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 "traffic.h"
#include <iostream>
#include <vector>
#include <functional>
using namespace std;
#define pb push_back
int LocateCentre(int N, int P[], int S[], int D[])
{
vector<vector<int>> adj(N);
for (int i = 0; i < N-1; ++i)
adj[S[i]].pb(D[i]), adj[D[i]].pb(S[i]);
vector<int> sz(N, 0);
vector<bool> vst(N, false);
function<int(int)> dfs = [&](int node)
{
vst[node] = true;
sz[node] = P[node];
for (int to : adj[node])
{
if (!vst[to])
sz[node] += sz[to];
}
return sz[node];
};
dfs(0);
int res = -1;
int best = 2e9 + 7;
for (int node = 0; node < N; ++node)
{
int tmp = 0;
for (int to : adj[node])
{
int ctr = sz[to];
if (sz[to] > sz[node])
ctr = sz[0] - sz[node];
tmp = max(tmp, ctr);
}
if (best > tmp)
{
best = tmp;
res = node;
}
}
return res;
}
# | 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... |