Submission #341735

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341735	2020-12-30T20:02:44 Z	ProUG	Traffic (IOI10_traffic)	C++14	Compilation error	0 ms	0 KB

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;
}

int main () {
    int n = 5;
    int p[5] = {10, 10, 10, 20, 20};
    int d[4] = {0, 1, 3, 4};
    int s[4] = {2, 2, 2, 3};

    cout << LocateCentre(n, p, d, s) << endl;
}

Compilation message

/tmp/ccULIEqy.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cck2140H.o:traffic.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status