Submission #385683

#	Time	Username	Problem	Language	Result	Execution time	Memory
385683		SansPapyrus683	Traffic (IOI10_traffic)	C++17	100 / 100	1347 ms	166124 KiB

traffic

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using std::cout;
using std::endl;
using std::vector;

vector<int> city_sub_num;
vector<int> parent;

int calc_sub_fans(int at, int prev, int P[], const vector<vector<int>>& neighbors) {
    city_sub_num[at] = P[at];
    parent[at] = prev;
    for (int n : neighbors[at]) {
        if (n != prev) {
            city_sub_num[at] += calc_sub_fans(n, at, P, neighbors);
        }
    }
    return city_sub_num[at];
}

int LocateCentre(int N, int P[], int S[], int D[]) {
    city_sub_num = vector<int>(N);
    parent = vector<int>(N);

    vector<vector<int>> neighbors(N);
    for (int i = 0; i < N - 1; i++) {
        neighbors[S[i]].push_back(D[i]);
        neighbors[D[i]].push_back(S[i]);
    }
    calc_sub_fans(0, 0, P, neighbors);

    int total_fans = 0;
    for (int i = 0; i < N; i++) {
        total_fans += P[i];
    }

    int min_congestion = INT_MAX;
    int best_center = -1;
    for (int i = 0; i < N; i++) {
        int this_max = total_fans - city_sub_num[i];
        for (int n : neighbors[i]) {
            if (parent[i] != n) {
                this_max = std::max(this_max, city_sub_num[n]);
            }
        }
        if (this_max < min_congestion) {
            min_congestion = this_max;
            best_center = i;
        }
    }
    return best_center;
}

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