(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #309265

#TimeUsernameProblemLanguageResultExecution timeMemory
309265rweiyzTraffic (IOI10_traffic)C++17
100 / 100
1310 ms156664 KiB
#include "traffic.h" #include <bits/stdc++.h> const int mx = 1e6; int fans; std::vector <int> adj[mx]; std::vector <int> children(mx),ppl(mx),nodes(mx); void dfs(int node,int parent){ for (auto x : adj[node]){ if (x == parent) continue; dfs(x,node); children[node] += children[x]; ppl[node] = std::max(ppl[node],children[x]); } ppl[node] = std::max(ppl[node],fans-children[node]-nodes[node]); children[node] += nodes[node]; } int LocateCentre(int n,int p[],int s[],int d[]){ for (int i = 0 ; i < n ; i++){ fans += p[i]; nodes[i] = p[i]; } for (int i = 0 ; i < n-1 ; i++){ adj[d[i]].push_back(s[i]); adj[s[i]].push_back(d[i]); } dfs(0,-1); int ans = INT_MAX; int res = -1; for (int i = 0 ; i < n ; i++){ if (ppl[i] < ans) { ans = ppl[i]; res = i; } } return res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...