# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
991075 | 2024-06-01T08:27:00 Z | borisAngelov | Traffic (IOI10_traffic) | C++17 | 5 ms | 33116 KB |
#include "traffic.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1000005; const long long inf = (1LL << 60); int n; int a[maxn]; vector<int> g[maxn]; long long ans[maxn]; long long subtreeSum[maxn]; long long down[maxn]; void dfs(int node, int par, int dep) { down[node] = 0; subtreeSum[node] = a[node]; for (int i = 0; i < g[node].size(); ++i) { int to = g[node][i]; if (to != par) { dfs(to, node, dep + 1); subtreeSum[node] += subtreeSum[to]; down[node] = max(down[node], subtreeSum[to]); } } } int LocateCentre(int N, int pp[], int S[], int D[]) { n = N; for (int i = 1; i <= n; ++i) { a[i] = pp[i - 1]; if (i == n) { break; } int x = S[i - 1]; int y = D[i - 1]; ++x; ++y; g[x].push_back(y); g[y].push_back(x); } long long ans = inf; for (int i = 1; i <= n; ++i) { dfs(i, -1, 0); ans = min(ans, down[i]); } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 33116 KB | Output is correct |
2 | Incorrect | 5 ms | 33116 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 33116 KB | Output is correct |
2 | Incorrect | 5 ms | 33116 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 33116 KB | Output is correct |
2 | Incorrect | 5 ms | 33116 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 33116 KB | Output is correct |
2 | Incorrect | 5 ms | 33116 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |