Cod sursa(job #2781895)

Utilizator johnny7577Ion Vasile johnny7577 Data 10 octombrie 2021 20:57:47
Problema Cerere Scor 65
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream in("cerere.in");
ofstream out("cerere.out");
int n,a,b,root;
const int dim=1e5+10;
vector<vector<int>> adj;
vector<int> ans,lvl,val;
bitset<dim> outer;

void dfs(int u, int nivel)
{
    lvl[nivel]=u;
    if(val[u])
        ans[u]=ans[lvl[nivel-val[u]]]+1;
    for(int v:adj[u])
        dfs(v,nivel+1);
}

int main() {
    in>>n;
    adj.resize(n+1);
    val.resize(n+1);
    ans.resize(n+1);
    lvl.resize(n+1);
    for(int i=1;i<=n;i++)
        in>>val[i];
    for(int i=1;i<=n-1;i++)
    {
        in>>a>>b;
        outer[b]=true;
        adj[a].push_back(b);
    }
    for(int i=1;i<=n;i++)
    {
        if(outer[i]==false)
        {
            root=i;
            break;
        }
    }
    dfs(root,1);
    for(int i=1;i<=n;i++)
        out<<ans[i]<<" ";
    return 0;
}