Submission #546314

#	Time	Username	Problem	Language	Result	Execution time	Memory
546314		krit3379	Traffic (IOI10_traffic)	C++17	100 / 100	1147 ms	166772 KiB

traffic

#include<bits/stdc++.h>
using namespace std;
#define N 1000005

int cnt[N],mi=2e9,ans;
vector<int> g[N];

void dfs(int s,int f,int *p){
    cnt[s]=p[s];
    for(auto x:g[s]){
        if(x==f)continue;
        dfs(x,s,p);
        cnt[s]+=cnt[x];
    }
}

void dfs2(int s,int f,int carry){
    int m=carry;
    for(auto x:g[s]){
        if(x==f)continue;
        dfs2(x,s,carry+cnt[s]-cnt[x]);
        m=max(m,cnt[x]);
    }
    if(m<mi)mi=m,ans=s;
}

int LocateCentre(int n, int p[N], int s[N], int d[N]) {
    int i,a,b;
    for(i=0;i<n-1;i++){
        a=s[i],b=d[i];
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(0,-1,p);
    dfs2(0,-1,0);
    return ans;
}

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