Submission #688337

#	Time	Username	Problem	Language	Result	Execution time	Memory
688337		sharaelong	Traffic (IOI10_traffic)	C++17	100 / 100	939 ms	170616 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 1e6 + 1;

vector<int> adj[MAX_N];
int sz[MAX_N];
int par[MAX_N];

void dfs(int here, int parent = -1) {
    par[here] = parent;
    for (int there: adj[here]) {
        if (there != parent) {
            dfs(there, here);
            sz[here] += sz[there];
        }
    }
}

int LocateCentre(int n, int pp[], int S[], int D[]) {
    for (int i=0; i<n-1; ++i) {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    for (int i=0; i<n; ++i) sz[i] = pp[i];
    dfs(0);

    int tot_sz = 0;
    int ans = 2e9 + 2;
    int location = -1;
    for (int i=0; i<n; ++i) tot_sz += pp[i];
    for (int i=0; i<n; ++i) {
        int max_congestion = 0;
        for (int there: adj[i]) {
            if (there == par[i]) {
                max_congestion = max(max_congestion, tot_sz - sz[i]);
            } else {
                max_congestion = max(max_congestion, sz[there]);
            }
        }
        if (ans > max_congestion) {
            ans = max_congestion;
            location = i;
        }
    }
    return location;
}

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