Submission #573378

#TimeUsernameProblemLanguageResultExecution timeMemory
573378Trisanu_DasTraffic (IOI10_traffic)C++17
100 / 100
966 ms158912 KiB
#include <bits/stdc++.h> #include "traffic.h" using namespace std; int peeps = 0; vector<int> adj[(int)1e6], city((int)1e6), peepsInPath((int)1e6), numOfChild((int)1e6); void dfs(int u, int parent){ for (auto v: adj[u]) { if (v == parent) continue; dfs(v, u); numOfChild[u] += numOfChild[v]; peepsInPath[u] = max(peepsInPath[u], numOfChild[v]); } peepsInPath[u] = max(peepsInPath[u], peeps - numOfChild[u] - city[u]); numOfChild[u] += city[u]; } int LocateCentre(int n, int p[], int s[], int d[]){ for(int i = 0; i < n; i++){ peeps += p[i]; city[i] = p[i]; } for(int i = 0; i < n - 1; i++){ adj[s[i]].push_back(d[i]); adj[d[i]].push_back(s[i]); } dfs(0, -1); int ans = -1, cong = INT_MAX; for(int i = 0; i < n; i++){ if(peepsInPath[i] < cong){ ans = i; cong = peepsInPath[i]; } } 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...