# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
766408 | 2023-06-25T15:51:32 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(n); 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 <void(int,int)> num=[&](int x,int y){ if(par[y]==x){ return tot[y]; } else{ return all-tot[x]; } }; dfs(0); p[0]=-1; ll mn=INF,ans=0; for(int i=0;i<n;i++){ ll curmin=INF; for(auto y:adj[i]){ curmin=min(curmin,num(i,y)); } if(curmin<mn){ mn=curmin; ans=i; } } return ans; }