Submission #1088837

#TimeUsernameProblemLanguageResultExecution timeMemory
1088837StefanSebezTraffic (IOI10_traffic)C++14
100 / 100
870 ms194336 KiB
#include "traffic.h" #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define ll long long #define ld long double const int N=1e6+50; const ll inf=1e18; vector<int>E[N]; int a[N],par[N],ind; ll dp[N],dp1[N],sajz[N],res=inf; void DFS1(int u,int parent){ par[u]=parent; sajz[u]=a[u]; for(auto i:E[u]){ if(i==parent) continue; DFS1(i,u); sajz[u]+=sajz[i]; dp[u]+=dp[i]+sajz[i]; } } void DFS(int u){ int v=par[u]; if(u!=0) dp1[u]=dp1[v]+dp[v]-dp[u]-sajz[u]+sajz[0]-sajz[u]; if(res>dp[u]+dp1[u]) ind=u; res=min(res,dp[u]+dp1[u]); for(auto i:E[u]){ if(i==par[u]) continue; DFS(i); } } int LocateCentre(int n, int pp[], int S[], int D[]) { for(int i=0;i<n;i++) a[i]=pp[i]; for(int i=0;i<n-1;i++){E[S[i]].pb(D[i]),E[D[i]].pb(S[i]);} DFS1(0,-1); DFS(0); //for(int i=0;i<n;i++) {for(auto j:E[i]) printf("%i ",j);printf("\n");} //for(int i=0;i<n;i++) printf("%i: %lld %lld %lld\n",i,dp[i],dp1[i],sajz[i]); return ind; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...