| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 372756 | Drew_ | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#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 = 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);
}
res = min(res, tmp);
}
return res;
}
int main()
{
int N;
cin >> N;
int A[N], S[N-1], D[N-1];
for (int i = 0; i < N; ++i)
cin >> A[i];
for (int i = 0; i < N-1; ++i)
cin >> S[i] >> D[i];
cout << LocateCentre(N, A, S, D) << '\n';
return 0;
}