제출 #636337

#제출 시각아이디문제언어결과실행 시간메모리
636337as111Traffic (IOI10_traffic)C++14
0 / 100
25 ms47188 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 - 1; i++) { total += P[i]; pop[i] = P[i]; adj[S[i]].push_back(D[i]); adj[D[i]].push_back(S[i]); } total += P[N - 1]; pop[N-1] = P[N - 1]; dfs(0, -1); int ansi = 0; 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]); if (mx < ans) { ans = mx; ansi = i; } } return ansi; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...