Submission #367111

#	Time	Username	Problem	Language	Result	Execution time	Memory
367111		quynx	Traffic (IOI10_traffic)	C++17	100 / 100	1207 ms	156012 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6;
const int INF = 2e9+1;

int fans = 0;
vector<int> nodes(MX), people(MX), child(MX), adj[MX];

void dfs(int parent, int node) {
    for (auto& u: adj[node]) {
        if (u == parent) continue;
        child[node] += nodes[u];
        dfs(node, u);
        child[node] += child[u];
        people[node] = max(people[node], child[u] + nodes[u]);
    }
    people[node] = max(people[node], fans - child[node] - nodes[node]);
}

int LocateCentre(int N, int P[], int S[], int D[]) {
    for (int i = 0; i < N; ++i) {
        fans += (nodes[i] = P[i]);
        if (i < N-1) {
            adj[S[i]].push_back(D[i]);
            adj[D[i]].push_back(S[i]);
        }
    }
    dfs(-1,0);
    int ans = -1, minC = INF;;
    for (int i = 0; i < N; ++i) {
        if (minC > people[i]) {
            ans = i;
            minC = people[i];
        }
    }
    //cout << minC << "\n";
    return ans;
}

//int main() {
    //ios_base::sync_with_stdio(false); cin.tie(nullptr);
    //int N, P[10000], S[10000], D[10000];
    //cin >> N;
    //for (int i = 0; i < N; ++i) cin >> P[i];
    //for (int i = 0; i < N - 1; ++i) cin >> S[i] >> D[i];
    //cout << LocateCentre(N,P,S,D) << "\n";
//}

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