# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
208593 | 2020-03-11T17:55:52 Z | DodgeBallMan | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include "traffic.h" using namespace std; const int N = 1e6 + 10; bool vis[N]; long long val[N], sum; vector<int> g[N]; long long dfs( int u, int p ) { for( int v : g[u] ) if( v != p ) val[u] += dfs( v, u ); return val[u]; } int LocateCentre(int N, int pp[], int S[], int D[]) { for ( int i = 0 ; i < N ; i++ ) val[i] = pp[i], sum += val[i]; for ( int i = 0 ; i < N - 1 ; i++ ) g[S[i]].emplace_back( D[i] ), g[D[i]].emplace_back( S[i] ); dfs( 0, -1 ); int ret; long long mn = 1e18; for ( int i = 0 ; i < N ; i++ ) { long long mx = sum - val[i]; for( int v : g[u] ) mx = max( mx, val[v] ); if( mn > mx ) mn = mx, ret = i; } return ret; }