Submission #278811

#	Time	Username	Problem	Language	Result	Execution time	Memory
278811		ec1117	Traffic (IOI10_traffic)	C++17	100 / 100	1248 ms	159100 KiB

traffic

#include "bits/stdc++.h"
#include "traffic.h"
using namespace std;

#define pb push_back
#define mp make_pair


vector<int> adj[1000001];
long long sum[1000001];
int pars[1000001];

void dfs(int n, int par){
    pars[n]=par;
    for(int x:adj[n]){
        if(x!=par) {
            dfs(x, n);
            sum[n] += sum[x];
        }
    }
}

int LocateCentre(int n, int p[], int s[], int d[]){//int[] s?
    for(int i=0;i<n;i++){
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    for(int i=0;i<n;i++){
        sum[i]=p[i];
    }
    dfs(0,0);
    int ret=0;
    long long mins=LLONG_MAX;
    for(int i=0;i<n;i++){
        long long tmp=0;
        for(int j:adj[i]){
            if(j!=pars[i]) {
                tmp = max(tmp, sum[j]);
            }
        }
        tmp=max(tmp,sum[0]-sum[i]);
        if(tmp<mins){
            mins=tmp;
            ret=i;
        }
    }
    return ret;
}

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