Submission #897530

#	Time	Username	Problem	Language	Result	Execution time	Memory
897530		Macker	Traffic (IOI10_traffic)	C++17	100 / 100	753 ms	155296 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()

// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx2")

int sm = 0;
vector<vector<int>> adj;
vector<int> sz;
vector<int> dp;

int dfs(int a, int p) {
    dp[a] = sz[a];
    for (auto &b : adj[a]) {
        if(b == p) continue;
        dp[a] += dfs(b, a);
    }
    return dp[a];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    sz.assign(pp, pp + N);
    adj.assign(N, {});
    dp.assign(N, 0);
    for (auto i : sz) sm += i;
    for (int i = 0; i < N - 1; i++) {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }

    dfs(0, 0);
    int mn = INT_MAX;
    int mnc = 0;
    for (int i = 0; i < N; i++) {
        int m = 0;
        int s = sz[i];
        for (auto &b : adj[i]) {
            if(dp[b] < dp[i]){
                m = max(m, dp[b]);
                s += dp[b];
            }
        }
        m = max(m, sm - s);
        if(m < mn){
            mn = m;
            mnc = i;
        }
    }
    return mnc;
}

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