HackerEarth Little Shino and K Ancestor problem solution

In this HackerEarth Little Shino and K Ancestor problem solution Assume that you are given an undirected rooted tree with N nodes and an integer K. Node 1 is the root of the tree. Each node is uniquely numbered from 1 to N. Additionally, each node also has a color and the color is an integer value.

Note: Different nodes can have the same color.

For each node, you are required to find the Kth closest ancestor from that node which has the same color.

HackerEarth Little Shino and K Ancestor problem solution.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 1e6 + 5;
int a[MAX], k, n, ans[MAX];
vector <int> v[MAX];
vector <int> adj[MAX];

void dfs(int from, int par) {
    if (v[a[from]].size() >= k) {
        int l = v[a[from]].size();
        ans[from] = v[a[from]][l - k];
    }
    else {
        ans[from] = -1;
    }
    for (int to : adj[from]) {
        if (to != par) {
            v[a[from]].push_back(from);
            dfs(to, from);
            v[a[from]].pop_back();
        }
    }
}

int main(int argc, char* argv[])
{
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    ios::sync_with_stdio(false);
    int x, y;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n-1; i++) {
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    dfs(1, -1);
    for (int i = 1; i <= n; i++) {
        if (i < n) cout << ans[i] << ' ';
        else cout << ans[i] << endl;
    }
    return 0;
}

Second solution

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
#define debug_flag 1
#else
#define debug_flag 0
#endif

  template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
  os << "[" << p.first << ", " << p.second << "]";
  return os;
}

  template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
  os << "[";
  bool first = true;
  for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
  {
    if (!first)
      os << ", ";
    first = false;
    os << *it;
  }
  os << "]";
  return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
  vector<string> v;
  stringstream ss(s);
  string x;
  while (getline(ss, x, c))
    v.emplace_back(x);
  return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
  string name = it -> substr((*it)[0] == ' ', it -> length());
  if (isalpha(name[0]))
    cerr << name  << " = " << a << " ";
  else
    cerr << name << " ";
  _print(++it, args...);
}

typedef long long int int64;

const int N = (int)1e6 + 100;

int n, k;
int c_list[N];
vector<int> s_list[N];
int ans_list[N];
vector<int> graph[N];

void dfs(int v, int p)
{
  int color = c_list[v];

  s_list[color].push_back(v);

  int s_size = (int)s_list[color].size();
  if (s_size > k) {
    ans_list[v] = s_list[color][s_size - k - 1] + 1;
  } else {
    ans_list[v] = -1;
  }

  for (int to : graph[v]) {
    if (to == p) {
      continue;
    }
    dfs(to, v);
  }

  s_list[color].pop_back();
}

int main()
{
#ifdef LOCAL
  freopen ("input.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &c_list[i]);
  }
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    a--;
    b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  dfs(0, -1);

  for (int i = 0; i < n; i++) {
    printf("%d ", ans_list[i]);
  }
  printf("n");

  return 0;
}

coding problems solutions