Submission #430745

#	Time	Username	Problem	Language	Result	Execution time	Memory
430745		four_specks	Traffic (IOI10_traffic)	C++17	100 / 100	1177 ms	170664 KiB

traffic

#include "traffic.h"

#include <bits/stdc++.h>

using namespace std;

int total;

vector<int> adj[1000000];

int traffic[1000000];

int acc[1000000];
int dfs(int P[], int u, int p)
{
    traffic[u] = 0;

    acc[u] = P[u];
    for (const int &v : adj[u])
    {
        if (v != p)
        {
            acc[u] += dfs(P, v, u);
            traffic[u] = max(traffic[u], acc[v]);
        }
    }
    traffic[u] = max(traffic[u], total - acc[u]);

    return acc[u];
}

int LocateCentre(int N, int P[], int S[], int D[])
{
    total = 0;
    for (int i = 0; i < N; i++)
        total += P[i];

    for (int j = 0; j < N - 1; j++)
        adj[S[j]].push_back(D[j]),
        adj[D[j]].push_back(S[j]);

    dfs(P, 0, -1);

    int city = -1;

    int min_traffic = INT_MAX;
    for (int i = 0; i < N; i++)
    {
        if (traffic[i] < min_traffic)
        {
            city = i;
            min_traffic = traffic[i];
        }
    }

    return city;
}

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