# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
411418 | 2021-05-25T09:31:31 Z | alextodoran | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
/** ____ ____ ____ ____ ____ ||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; }