Submission #1015732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015732		Ariadna	Traffic (IOI10_traffic)	C++14	100 / 100	735 ms	186452 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
#define pb push_back
#define ll long long

using namespace std;

vector<vector<int>> adj;
vector<ll> sum;

ll min_traffic, centre, total = 0;
int dfs(int u, int p, int* P) {
    sum[u] = P[u];
    ll traffic = 0;
    for (int v: adj[u]) {
        if (v == p) continue;
        sum[u] += dfs(v, u, P);
        traffic = max(traffic, sum[v]);
    }
    traffic = max(traffic, total-sum[u]);

    if (traffic < min_traffic) {
        min_traffic = traffic;
        centre = u;
    }

    return sum[u];
}

int LocateCentre(int N, int* P, int* S, int* D) {
    adj = vector<vector<int>>(N);
    sum = vector<ll>(N);
    for (int i = 0; i < N-1; ++i) {
        adj[S[i]].pb(D[i]);
        adj[D[i]].pb(S[i]);
    }
    
    for (int i = 0; i < N; ++i) total += P[i];

    min_traffic = 1e18, centre = -1;
    dfs(0, 0, P);
    return centre;
}

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