Submission #550992

#	Time	Username	Problem	Language	Result	Execution time	Memory
550992		Jomnoi	Traffic (IOI10_traffic)	C++17	100 / 100	1186 ms	168624 KiB

traffic

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

const int MAX_N = 1e6 + 10;
const int INF = 2e9 + 7;

int P[MAX_N], sum[MAX_N], max_congestion = INF, ans;
vector <int> graph[MAX_N];

int dfs(const int &u, const int &p) {
    sum[u] = P[u];
    for(auto v : graph[u]) {
        if(v != p) {
            sum[u] += dfs(v, u);
        }
    }
    return sum[u];
}

void dfs2(const int &u, const int &p, const int &ps) {
    int ma = ps;
    for(auto v : graph[u]) {
        if(v == p) {
            continue;
        }

        ma = max(ma, sum[v]);
        dfs2(v, u, sum[u] + ps - sum[v]);
    }

    if(max_congestion > ma) {
        max_congestion = ma;
        ans = u;
    }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    for(int i = 1; i <= N; i++) {
        P[i] = pp[i - 1];
    }
    for(int i = 0; i < N - 1; i++) {
        S[i]++, D[i]++;
        graph[S[i]].push_back(D[i]);
        graph[D[i]].push_back(S[i]);
    }

    dfs(1, -1);
    dfs2(1, -1, 0);

    return ans - 1;
}

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