This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
const int mxN = 1000005;
vector<int> adj[mxN];
int sums[mxN], res[mxN];
void dfs(int u, int par, int p[]) {
sums[u] = p[u], res[u] = INT_MIN;
for(auto &v : adj[u]) {
if(v == par) continue;
dfs(v, u, p);
sums[u] += sums[v];
res[u] = max(res[u], sums[v]);
}
res[u] = max(res[u], sums[0]-sums[u]);
}
int LocateCentre(int n, int p[], int s[], int d[]) {
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, p);
int ans = INT_MAX, pos;
for(int i = 0; i < n; i++) {
if(ans > res[i])
ans = res[i], pos = i;
}
return pos;
}
Compilation message (stderr)
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:31:12: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
31 | return pos;
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |