Submission #614664

#	Time	Username	Problem	Language	Result	Execution time	Memory
614664		kbk0421	Traffic (IOI10_traffic)	C++17	100 / 100	918 ms	167700 KiB

traffic

#include <iostream>
#include <vector>
#include <numeric>
#define INF 1e9

using namespace std;

vector<int> G[1000010];
int d[1000010];
bool visited[1000010];
int sum;
int mn = INF;
int ans;

int dfs(int x, int *P)
{
    visited[x] = 1;
    int &ret = d[x] = P[x];
    int mx = 0;

    for(auto &p : G[x]){
        if(visited[p]) continue;
        int s = dfs(p,P);
        ret += s;
        mx = max(s, mx);
    }
    mx = max(sum-ret, mx);

    if(mx<mn){
        mn = mx;
        ans = x;
    }
    return ret;
}

int LocateCentre(int N, int P[], int S[], int D[])
{
    for(int i=0; i<N-1; i++){
        G[S[i]].push_back(D[i]);
        G[D[i]].push_back(S[i]);
    }
    sum = accumulate(P,P+N,0);

    dfs(0,P);
    return ans;
}

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