# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
332853 | 2020-12-03T18:47:33 Z | Dan4Life | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
#include "traffic.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; //#define int ll #define pb push_back #define mp make_pair #define fir first #define sec second #define all(a) a.begin(), a.end() const int maxn = 200010; const ll MOD = 1e9+7; const int INF = 1e9; const ll LINF = 1e18; ll n, m, a[maxn], b[maxn]; //map<int, int> M, N; string s, ss; //set<int> S; ll dis = LINF, ind = -1; vector<ll> adj[maxn]; ll subtree[maxn], ppl[maxn], fans = 0; void dfs(ll s, ll p=-1) { for(auto u : adj[s]) { if(u==p)continue; dfs(u,s), subtree[s]+=subtree[u]; ppl[s] = max(ppl[s], subtree[u]); } ppl[s] = max(ppl[s], fans-subtree[s]-a[s]); subtree[s]+=a[s]; } ll LocateCentre(int N, int pp[], int S[], int D[]) { ll i; for(i = 0; i < N-1; i++) a[i]=pp[i], adj[S[i]].pb(D[i]), adj[D[i]].pb(S[i]), fans+=a[i]; a[N-1]=pp[N-1], fans+=a[N-1]; dfs(0); for(i = 0; i < N; i++) if(dis>pp[i])dis=pp[i],ind=i; return ind; }