Submission #567631

#	Time	Username	Problem	Language	Result	Execution time	Memory
567631		losmi247	Traffic (IOI10_traffic)	C++14	100 / 100	977 ms	178528 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+56;

int n;
vector <int> g[N];
ll w[N];
ll subsum[N],celasuma = 0;
int najb = 0;
ll vr = 7e18;

void dfs(int x,int par){
    subsum[x] = w[x];
    ll cong = 0;
    for(auto f : g[x]){
        if(f == par) continue;
        dfs(f,x);
        cong = max(cong,subsum[f]);
        subsum[x] += subsum[f];
    }
    cong = max(cong,celasuma-subsum[x]);

    if(cong < vr){
        vr = cong;
        najb = x;
    }
}

int LocateCentre(int br1,int *P,int *S,int *D){
    n = br1;
    for(int i = 0; i <= n; i++){
        g[i].clear();
    }
    for(int i = 0; i < n; i++) w[i+1] = P[i];
    for(int i = 0; i < n-1; i++){
        g[S[i]+1].push_back(D[i]+1);
        g[D[i]+1].push_back(S[i]+1);
    }

    celasuma = 0;
    for(int i = 1; i <= n; i++) celasuma += w[i];
    dfs(1,0);

    return najb-1;
}

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