# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
766415 | 2023-06-25T15:57:28 Z | irmuun | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include "traffic.h" using namespace std; #define pb push_back #define ll long long #define ff first #define ss second #define all(s) s.begin(),s.end() const int maxn=1e6; const ll INF=1e18; vector<int>adj[maxn],used(maxn,0),par(maxn); ll tot[maxn]; int LocateCentre(int N, int P[], int S[], int D[]) { ll all=0; for(int i=0;i<N-1;i++){ adj[S[i]].pb(D[i]); adj[D[i]].pb(S[i]); } for(int i=0;i<N;i++){ all+=P[i]; } function <void(int)> dfs=[&](int x){ used[x]=1; tot[x]+=P[x]; for(auto y:adj[x]){ if(used[y]==0){ par[y]=x; dfs(y); tot[x]+=P[y]; } } }; function <ll(int,int)> num=[&](int x,int y){ if(par[y]==x){ return tot[y]; } else{ return all-tot[x]; } }; dfs(0); par[0]=-1; ll mn=INF; int ans=0; for(int i=0;i<N;i++){ ll cur=0; for(auto y:adj[i]){ cur=max(curmin,num(i,y)); } if(cur<mn){ mn=cur; ans=i; } } return ans; }