Submission #341726

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
341726	2020-12-30T19:41:51 Z	ProUG	Traffic (IOI10_traffic)	C++14	Compilation error	0 ms	0 KB

traffic

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

vector<int> adj[1000000];
int population_below[100005];
int population[100005];
int highest_traffic[1000005];

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_below[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_below[child];
            current_ans = max(current_ans, population_below[child]);
        }
    }

    highest_traffic[node] = current_ans;

    for (auto child : adj[node]) {
        if (child != parent) {
            dfs(child, node, overload + population[node] + children_population - p[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, s);
    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_traffic = i;
        }
    }

    return lowest_index;
}

Compilation message

traffic.cpp:1:10: fatal error: traffics.h: No such file or directory
    1 | #include "traffics.h"
      |          ^~~~~~~~~~~~
compilation terminated.