Submission #1275523

#TimeUsernameProblemLanguageResultExecution timeMemory
1275523kawhietTraffic (IOI10_traffic)C++20
100 / 100
621 ms164932 KiB
#include <bits/stdc++.h> #include "traffic.h" using namespace std; constexpr int N = 1e6 + 1; vector<int> a; int64_t sz[N], parent[N]; vector<int> g[N]; void dfs(int u, int p) { sz[u] += a[u]; parent[u] = p; for (auto v : g[u]) { if (v != p) { dfs(v, u); sz[u] += sz[v]; } } } int LocateCentre(int n, int A[], int s[], int d[]) { a.resize(n); for (int i = 0; i < n; i++) { a[i] = A[i]; } for (int i = 0; i < n - 1; i++) { g[s[i]].push_back(d[i]); g[d[i]].push_back(s[i]); } dfs(0, -1); int64_t sum = accumulate(a.begin(), a.end(), 0LL); int mn = 2e9, ans = -1; for (int u = 0; u < n; u++) { int64_t cur = 0; for (auto v : g[u]) { if (v == parent[u]) { cur = max(cur, sum - sz[u]); } else { cur = max(cur, sz[v]); } } if (cur < mn) { mn = cur; ans = u; } } 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...