Submission #491571

#TimeUsernameProblemLanguageResultExecution timeMemory
491571niloyrootTraffic (IOI10_traffic)C++14
0 / 100
0 ms204 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<ll>; using pl = pair<ll,ll>; #define pb push_back #define form(m,it) for(auto it=m.begin(); it!=m.end(); it++) #define forp(i,a,b) for(ll i=a; i<=b; i++) #define forn(i,a,b) for(ll i=a; i>=b; i--) #define newl '\n' #define ff first #define ss second const ll mod = 1000000007; int LocateCentre(int n, int p[], int s[], int d[]){ vi adj[n+1]; forp(i,0,n-2){ adj[s[i]].pb(d[i]); adj[d[i]].pb(s[i]); } ll sub[n]={0}; function<void(ll,ll)> dfs1 = [&](ll i, ll pa){ sub[i]+=p[i]; for(auto u:adj[i]){ if(u!=pa){ dfs1(u,i); sub[i]+=sub[u]; } } }; dfs1(0,-1); ll ans=0; ll temp=sub[0]-p[0]; function<void(ll,ll,ll)> dfs2 = [&](ll i, ll pa, ll curr){ if(curr<temp){ ans=i; temp=curr; } cout<<i<<" "<<curr<<newl; for(auto u:adj[i]){ if(u!=pa){ dfs2(u,i,curr+sub[0]-2*sub[u]); } } }; dfs2(0,-1,sub[0]-p[0]); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...