제출 #491573

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491573		niloyroot	Traffic (IOI10_traffic)	C++14	100 / 100	1239 ms	202020 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pl = pair<ll,ll>;
#define pb push_back
#define form(m,it) for(auto it=m.begin(); it!=m.end(); it++)
#define forp(i,a,b) for(ll i=a; i<=b; i++)
#define forn(i,a,b) for(ll i=a; i>=b; i--)
#define newl '\n'
#define ff first
#define ss second
const ll mod = 1000000007;
 
int LocateCentre(int n, int p[], int s[], int d[]){
    vi adj[n+1];
    forp(i,0,n-2){
        adj[s[i]].pb(d[i]);
        adj[d[i]].pb(s[i]);
    }
 
    ll sub[n]={0};
    function<void(ll,ll)> dfs1 = [&](ll i, ll pa){
        sub[i]+=p[i];
        for(auto u:adj[i]){
            if(u!=pa){
                dfs1(u,i);
                sub[i]+=sub[u];
            }
        }
    };
    dfs1(0,-1);
 
    ll ans=0;
    ll temp=sub[0]-p[0];
    function<void(ll,ll,ll)> dfs2 = [&](ll i, ll pa, ll curr){
        if(curr<temp){
            ans=i;
            temp=curr;
        }
        for(auto u:adj[i]){
            if(u!=pa){
                dfs2(u,i,curr+sub[0]-2*sub[u]);
            }
        }
    };
    dfs2(0,-1,sub[0]-p[0]);
 
    return ans;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25