Cod sursa(job #2324356)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 20 ianuarie 2019 16:51:32
Problema Cerere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("cerere.in");
ofstream g("cerere.out");

const int MAX = 1e5 + 10;

int n, root;
int ancestors[MAX], solution[MAX];
bool visited[MAX], is_son[MAX];
vector<int> v, monkey[MAX];

void Read()
{
    int A, B;
    f >> n;

    for(int i = 1; i <= n; ++i)
        f >> ancestors[i];
    for(int i = 1; i  < n; ++i)
    {
        f >> A >> B;
        is_son[B] = 1;
        monkey[A].push_back(B);
    }
    for(int i = 1; i <= n; ++i)
        if(!is_son[i])
        {
            root = i;
            break;
        }
}

void DFS(int node)
{
    v.push_back(node);

    // Verificam cu cati stramosi ne intoarcem, daca nu este maimuta inteligenta
    if(ancestors[node])
        solution[node] = 1 + solution[v[(v.size() - 1) - ancestors[node]]];

    for(int i = 0; i < monkey[node].size(); ++i)
        DFS(monkey[node][i]);

    v.pop_back();

}

void Print()
{
    for(int i = 1; i <= n; ++i)
        g << solution[i] << " ";
}

int main()
{
    Read();
    DFS(root);
    Print();
    return 0;
}