Codechef_August_Long/CHEFCOMP.cpp at master · CodeDistributor/Codechef_August_Long · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include<bits/stdc++.h>
using namespace std;


int main() {
    long long int t;
    cin>>t;

    while(t--){
       long long int n;
       cin>>n;

       unordered_map<long long int,int> g[n+1];
       long long int p[n+1];
       long long int a[n+1];
       long long int b[n+1];

       long long int d[n+1];

        for(long long int i=0;i<=n;i++){
           d[i]=-1;
        }

       for(long long int i=1;i<=n-1;i++){
           long long int u,v;
           cin>>u>>v;

            g[u][v]=1;
            g[v][u]=1;
       }

       for(long long int i=1;i<=n;i++){
           cin>>p[i];
       }

        for(long long int i=1;i<=n;i++){
           cin>>a[i];
       }

        for(long long int i=1;i<=n;i++){
           cin>>b[i];
       }

       for(long long int i=1;i<=n;i++){
           long long int visited[n+1] = {0};
           long long int city = p[i];

           stack<long long int> q;
           q.push(city);

           while(!q.empty()){
               long long int source = q.top();
               q.pop();


              if(visited[source]){
                  continue;
              }else{
                  visited[source]=1;

                   b[source] = b[source] - min(a[city],b[source]);
                    if(b[source]<=0 && d[source]==-1){
                         d[source] = i;
                    }
              }

               for(auto child : g[source]){
                  if(child.second && !visited[child.first]){
                       q.push(child.first);
                  }
               }
           }

            for(auto child : g[city]){
                g[city][child.first]=0;
                g[child.first][city]=0;


            }

       }
       for(long long int i=1;i<=n;i++){
           cout<<d[i]<<" ";
       }

       cout<<"\n";
    }
  return 0;
}