Submission #367097

#	Time	Username	Problem	Language	Result	Execution time	Memory
367097		quynx	Traffic (IOI10_traffic)	C++17	50 / 100	515 ms	160492 KiB

traffic

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

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

void dfs(int parent, int node) {
    int tmp = 0;
    for (auto& u: adj[node]) {
        if (u == parent) continue;
        tmp += nodes[u];
        dfs(node, u);
        tmp += child[u];
        child[node] += tmp;
        people[node] = max(people[node], child[u] + nodes[u]);
    }
    people[node] = max(people[node], fans - tmp - 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 = 0, minC = INF;;
    for (int i = 0; i < N; ++i) {
        if (minC > people[i]) {
            ans = i;
            minC = people[i];
        }
    }
    return ans;
}

//int main() {
    //ios_base::sync_with_stdio(false); cin.tie(nullptr);
    //int N = 5, P[] = {10,10,10,20,20}, S[] = {0,1,2,3}, D[] = {2,2,3,4};
    //cout << LocateCentre(N,P,S,D) << "\n";
//}

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