Submission #426607

#	Time	Username	Problem	Language	Result	Execution time	Memory
426607		proma	Traffic (IOI10_traffic)	C++17	100 / 100	1556 ms	157152 KiB

traffic

#include <bits/stdc++.h>
#define see(x) cerr<<#x<<"="<<x<<"\n";

using namespace std;

vector <int> sum, max_edge, last_edge;
vector <vector <int>> g;

void dfs (int v, int par, int P[]) {
    sum[v] = 0;
    max_edge[v] = 0;
    for (auto i: g[v]) {
        if (i != par) {
            dfs(i, v, P);
            sum[v] += sum[i] + P[i];
            max_edge[v] = max(max_edge[v], sum[i] + P[i]);
        }
    }
}

void dfs_for_last_edge (int v, int par, int P[]) {
    for (auto i: g[v]) {
        if (i != par) {
            last_edge[i] = sum[v] + P[v] + last_edge[v] - sum[i] - P[i];
            dfs_for_last_edge(i, v, P);
        }
    }
}

int LocateCentre (int N, int P[], int S[], int D[]) {
    g.resize(N);
    sum.resize(N);
    max_edge.resize(N);
    last_edge.resize(N);

    for (int i = 0; i < N - 1; i ++) {
        g[S[i]].push_back(D[i]);
        g[D[i]].push_back(S[i]);
    }

    last_edge[0] = 0;
    dfs(0, -1, P);
    dfs_for_last_edge(0, -1, P);

    int min_res = max_edge[0], ans = 0;
    for (int i = 1; i < N; i ++) {
        int cur = max(max_edge[i],  last_edge[i]);
        if (cur < min_res) {
            min_res = cur;
            ans = i;
        }
    }

    return ans;
}

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