Submission #1064698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064698		ArthuroWich	Traffic (IOI10_traffic)	C++17	100 / 100	749 ms	178568 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[1000005];
long long int n, a[1000005], s[1000005], ans = -1, ma = INT64_MAX;
void dfs(int i, int p) {
    s[i] = a[i];
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfs(j, i);
        s[i] += s[j];
    }
}
void dfsc(int i, int p, long long int ps) {
    long long int t = a[i], v = ps;
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        t += s[j];
        v = max(v, s[j]);
    }
    if (ma > v) {
        ma = v;
        ans = i;
    }
    for (int j : adj[i]) {
        if (j == p) {
            continue;
        }
        dfsc(j, i, ps+t-s[j]);
    }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = N;
    for (int i = 0; i < n; i++) {
        a[i] = pp[i];
    }
    for (int i = 0; i < n-1; i++) {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    dfs(0, -1);
    dfsc(0, -1, 0);
    return ans;
}

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