| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 411420 | alextodoran | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
int n;
int p[N_MAX];
int subSize[N_MAX];
vector <int> edges[N_MAX];
int parent[N_MAX];
void dfs (int u)
{
subSize[u] = p[u];
for(int v : edges[u])
if(v != parent[u])
{
parent[v] = u;
dfs(v);
subSize[u] += subSize[v];
}
}
int LocateCenter (int N, int* P, int* X, int* Y)
{
n = N;
for(int u = 0; u < n; u++)
p[u] = P[u];
for(int i = 0; i < n - 1; i++)
{
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
parent[0] = -1;
dfs(0);
int best = INT_MAX;
int answer = -1;
for(int u = 0; u < n; u++)
{
int maxFlow = subSize[0] - subSize[u];
for(int v : edges[u])
if(v != parent[u])
maxFlow = max(maxFlow, subSize[v]);
if(maxFlow < best)
{
best = maxFlow;
answer = u;
}
}
return answer;
}