Submission #199322

#	Time	Username	Problem	Language	Result	Execution time	Memory
199322		mythos	Traffic (IOI10_traffic)	C++14	100 / 100	1905 ms	166904 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

vector<int> adj[1000100];
int n, opt, a[1000100];
long long res = 1e18, sum = 0;

long long cal(int x, int pa) {
    long long mv = 0, s = 0;
    for (int i = 0; i < (int) adj[x].size(); i++) {
        if (adj[x][i] == pa) continue;
        long long t = cal(adj[x][i], x);
        s += t;
        mv = max(mv, t);
    }
    s += a[x];
    mv = max(mv, sum - s);
    if (res > mv) {
        res = mv; opt = x;  
    }
    return s;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        a[i] = pp[i];
        sum += a[i];
    }
    for (int i = 0; i < n - 1; i++) {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    cal(0, -1);
    return opt;
}

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