Submission #373914

#	Time	Username	Problem	Language	Result	Execution time	Memory
373914		rainliofficial	Traffic (IOI10_traffic)	C++11	100 / 100	1179 ms	172524 KiB

traffic

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

const int maxN = 1e6;
const int maxC = 2e9;
vector<int> arr[maxN];
int fans = 0;
int children[maxN];
int ans[maxN];
int node[maxN];

void dfs(int curr, int parent){
    for (int index : arr[curr]){
        if (index != parent){
            dfs(index, curr);
            // add the number of children for my children (subtree)
            children[curr] += children[index];
            ans[curr] = max(ans[curr], children[index]); // select the grestest subtree
        }
    }
    ans[curr] = max(ans[curr], fans - node[curr] - children[curr]);
    children[curr] += node[curr];
}

int LocateCentre(int n, int p[], int s[], int d[]){
    for (int i=0; i<n; i++){
        fans += p[i];
        node[i] = p[i];
    }
    for (int i=0; i<n-1; i++){
        arr[s[i]].push_back(d[i]);
        arr[d[i]].push_back(s[i]);
    }
    // start dfs and find subtree fans
    dfs(0, -1);
    int out = 0;
    int sol = 2e9;
    for (int i=0; i<n; i++){
        if (ans[i] < sol){
            sol = ans[i];
            out = i;
        }
    }
    return out;
}

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