Submission #636332

#TimeUsernameProblemLanguageResultExecution timeMemory
636332as111Traffic (IOI10_traffic)C++14
0 / 100
23 ms47256 KiB
#include <traffic.h> #include <vector> #define MAXN 1000000 using namespace std; int pop[MAXN]; vector<int> vals[MAXN];// amt congestion for each path coming out vector<int> adj[MAXN]; int total = 0; // total people everywhere int ans = 2000001; int dfs(int x, int y) {//y is back edge int amt = pop[x]; for (int e : adj[x]) { if (e == y) continue; int edge = dfs(e, x); vals[x].push_back(edge); amt += edge; } return amt; } int LocateCentre(int N, int P[], int S[], int D[]) { for (int i = 0; i < N; i++) { total += P[i]; pop[i] = P[i]; adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } dfs(0, -1); for (int i = 0; i < N; i++) { int mx = 0; int amt = 0; for (int val : vals[i]) { mx = max(mx, val); amt += val; } mx = max(mx, total - amt - pop[i]); ans = min(ans, mx); } 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...