제출 #957068

#제출 시각아이디문제언어결과실행 시간메모리
957068MuntherCarrotTraffic (IOI10_traffic)C++14
50 / 100
328 ms178552 KiB
#include <bits/stdc++.h> #include "traffic.h" using namespace std; #define ll long long const int MAXN = 1e6 + 10; vector<vector<int>> vtx(MAXN); ll a[MAXN], mx[MAXN]; ll dfs(int u, int p, ll cnt){ ll sum = 0; mx[u] = cnt; for(int v : vtx[u]){ if(v == p) continue; ll res = dfs(v, u, cnt + a[u]); mx[u] = max(mx[u], res); sum += res; } return sum + a[u]; } int LocateCentre(int N, int P[], int S[], int D[]){ for(int i = 0; i < N; i++){ a[i] = P[i]; } for(int i = 0; i < N - 1; i++){ vtx[S[i]].push_back(D[i]); vtx[D[i]].push_back(S[i]); } dfs(0, 0, 0); int ans = 0; for(int i = 1; i < N; i++){ if(mx[i] < mx[ans]){ ans = i; } } return ans; } // by me
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...