Cod sursa(job #2639741)

Utilizator eugen5092eugen barbulescu eugen5092 Data 3 august 2020 17:17:30
Problema Cerere Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<bits/stdc++.h>
using namespace std;

ifstream ci("cerere.in");
ofstream cou("cerere.out");

vector<int>v[100005];
int linie[100005];
int dp[100005];
int stramos[100005];
int n,m;

void Dfs(int nod){
    if(m==0||stramos[nod]==0){
        linie[++m]=nod;
    }else{
        dp[nod]=dp[linie[m-stramos[nod]+1]]+1;
        linie[++m]=nod;
    }

    //cout<<" ---\n";
    //cout<<nod<<" "<<dp[nod]<<" "<<dp[linie[m-stramos[nod]]]<<"\n";
    for(auto i:v[nod]){
        Dfs(i);
    }
    m--;
}

void citire(){
    ci>>n;
    int a,b;
    for(int i=1;i<=n;i++){
        ci>>stramos[i];
    }
    dp[1]=0;
    for(int i=1;i<=n;i++){
        ci>>a>>b;
        v[a].push_back(b);

    }
}

void rez(){
    int i;
    Dfs(1);
    for(i=1;i<=n;i++){
        cou<<dp[i]<<" ";
    }
}

int main()
{
    citire();
    rez();
    return 0;
}