# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
277090 | 2020-08-21T02:59:15 Z | Bill_00 | Traffic (IOI10_traffic) | C++14 | 21 ms | 31616 KB |
#include <traffic.h> #include <bits/stdc++.h> using namespace std; vector<long long>adj[1000000]; vector<long long>leaf; long long p[1000000]; long long sum[1000000]; long long dp[1000000],vis[1000000]; void dfs(int j){ if(adj[j].size()==1 && p[j]==adj[j][0]){ leaf.push_back(j); return; } for(int i=0;i<adj[j].size();i++){ if(adj[j][i]!=p[j]){ p[adj[j][i]]=j; dfs(adj[j][i]); } } } void check(int j){ vis[j]=1; for(int i=0;i<adj[j].size();i++){ if(vis[adj[j][i]]==0 && adj[j][i]!=p[j]){ dp[adj[j][i]]=dp[j]-(2*sum[adj[j][i]])+sum[0]; check(adj[j][i]); } } if(j!=0){ dp[p[j]]=dp[j]+2*sum[j]-sum[0]; check(p[j]); } } long long calc(long long j,int a[]){ sum[j]=(long long)a[j]; for(int i=0;i<adj[j].size();i++){ if(adj[j][i]!=p[j]){ sum[j]+=calc(adj[j][i],a); } } return sum[j]; } int LocateCentre(int n,int a[],int s[],int d[]){ memset(vis,0,sizeof(vis)); for(int i=0;i<n-1;i++){ adj[s[i]].push_back(d[i]); adj[d[i]].push_back(s[i]); } p[0]=-1; dfs(0); calc(0,a); dp[leaf[0]]=0; int ans=0,id=0; check(leaf[0]); for(int i=1;i<n;i++){ if(dp[i]<ans){ id=i; ans=dp[i]; } } return id; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 31616 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 31616 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 31616 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 21 ms | 31616 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |