Submission #957073

#	Time	Username	Problem	Language	Result	Execution time	Memory
957073		MuntherCarrot	Traffic (IOI10_traffic)	C++14	100 / 100	794 ms	184192 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"

using namespace std;

#define ll long long

const int MAXN = 1e6 + 10;
vector<vector<int>> vtx(MAXN);
ll a[MAXN], mx[MAXN], son[MAXN];
ll all;

void dfs(int u, int p){
    for(int v : vtx[u]){
        if(v == p) continue;
        dfs(v, u);
        mx[u] = max(mx[u], son[v]);
        son[u] += son[v];
    }
    son[u] += a[u];
    mx[u] = max(mx[u], all - son[u]);
}

int LocateCentre(int N, int P[], int S[], int D[]){
    all = accumulate(P, P + N, 0ll);
    for(int i = 0; i < N; i++){
        a[i] = P[i];
    }
    for(int i = 0; i < N - 1; i++){
        vtx[S[i]].push_back(D[i]);
        vtx[D[i]].push_back(S[i]);
    }
    dfs(0, 0);
    int ans = 0;
    for(int i = 1; i < N; i++){
        if(mx[i] < mx[ans]){
            ans = i;
        }
    }
    return ans;
}

// by me

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