Submission #341736

#	Time	Username	Problem	Language	Result	Execution time	Memory
341736		ProUG	Traffic (IOI10_traffic)	C++14	100 / 100	1344 ms	174828 KiB

traffic

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1000000];
int population_cumulative[1000000];
int population[1000000];
int highest_traffic[1000000];

int calculate_population (int node, int parent) {
    int total_population = population[node];
    for (auto child : adj[node]) {
        if (child != parent) {
            total_population += calculate_population(child, node);
        }
    }

    population_cumulative[node] = total_population;
    return total_population;
}

void dfs (int node, int parent, int overload) {
    int current_ans = overload;
    int children_population = 0;

    for (auto child : adj[node]) {
        if (child != parent) {
            children_population += population_cumulative[child];
            current_ans = max(current_ans, population_cumulative[child]);
        }
    }

    highest_traffic[node] = current_ans;

    for (auto child : adj[node]) {
        if (child != parent) {
            dfs(child, node, overload + population[node] + children_population - population_cumulative[child]);
        }
    }
}

int LocateCentre (int n, int p[], int d[], int s[]) {
    int root = 0;
    for (int i = 0; i < n; i++) {
        population[i] = p[i];
    }

    for (int i = 0; i < n-1; i++) {
        int a, b;
        a = d[i];
        b = s[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    calculate_population(root, -1);
    dfs(root, -1, 0);

    int lowest_traffic = INT_MAX, lowest_index = 0;
    for (int i = 0; i < n; i++) {
        if (highest_traffic[i] < lowest_traffic) {
            lowest_traffic = highest_traffic[i];
            lowest_index = i;
        }
    }

    return lowest_index;
}

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