Submission #380445

#	Time	Username	Problem	Language	Result	Execution time	Memory
380445		ruadhan	Traffic (IOI10_traffic)	C++14	100 / 100	1182 ms	174700 KiB

traffic

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 1, INF = 2e9 + 2;
vector<int> adj[MAXN], population(MAXN), maxCongestion(MAXN), children(MAXN);
int total_people = 0;

void dfs(int s, int p)
{
    for (auto u : adj[s])
    {
        if (u == p)
            continue;
        dfs(u, s);
        children[s] += children[u];
        maxCongestion[s] = max(maxCongestion[s], children[u]);
    }
    children[s] += population[s];
    maxCongestion[s] = max(maxCongestion[s], total_people - children[s]);
}

int LocateCentre(int N, int P[], int S[], int D[])
{
    for (int i = 0; i < N - 1; i++)
    {
        population[i] = P[i];
        total_people += P[i];
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    population[N - 1] = P[N - 1];
    total_people += P[N - 1];

    dfs(0, -1);

    int ans = -1, bestCongestion = INF;
    for (int i = 0; i < N; i++)
    {
        if (maxCongestion[i] < bestCongestion)
        {
            ans = i;
            bestCongestion = maxCongestion[i];
        }
    }
    return ans;
}

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