HackerEarth Mancunian And Colored Tree problem solution

In this HackerEarth Mancunian And Colored Tree problem solution After a hectic week at work, Mancunian and Liverbird decide to go on a fun weekend camping trip. As they were passing through a forest, they stumbled upon a unique tree of N nodes. Vertices are numbered from 1 to N.

Each node of the tree is assigned a color (out of C possible colors). Being bored, they decide to work together (for a change) and test their reasoning skills. The tree is rooted at vertex 1. For each node, they want to find its closest ancestor having the same color.

HackerEarth Mancunian And Colored Tree problem solution.

#include <iostream>
#include <stack>
#include <vector>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;


#define SIZE 100005
int n, C, col[SIZE], ans[SIZE];
vector<int> adj[SIZE];
stack<int> st[SIZE];


void dfs(int v){

    if(st[col[v]].empty()){
        ans[v] = -1;
    }
    else{
        ans[v] = st[col[v]].top();
    }

    st[col[v]].push(v);

    for(int i=0;i<(int)adj[v].size();i++){
        int vv = adj[v][i];
        dfs(vv);
    }

    st[col[v]].pop();
}


int main(){

    cin>>n>>C;
    for(int i=2;i<=n;i++){
        int p;
        cin>>p;
        adj[p].pb(i);
    }
    for(int i=1;i<=n;i++)
        cin>>col[i];

    dfs(1);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector <int> G[MAXN], col_list[MAXN];
int col[MAXN], ans[MAXN];
void dfs(int pos)
{
    if(col_list[col[pos]].empty())
        ans[pos] = -1;
    else
        ans[pos] = col_list[col[pos]].back();
    col_list[col[pos]].push_back(pos);
    for (int i = 0; i < G[pos].size(); ++i)
    {
        dfs(G[pos][i]);
    }
    col_list[col[pos]].pop_back();
}
int main()
{
    int n,c;
    cin>>n>>c;
    for (int i = 2; i <= n; ++i)
    {
        int par;
        cin>>par;
        G[par].push_back(i);
    }
    for (int i = 1; i <= n; ++i)
    {
        cin>>col[i];
    }
    dfs(1);
    for (int i = 1; i <= n; ++i)
    {
        cout<<ans[i]<<" ";
    }
    return 0;
}

coding problems solutions