Submission #796905

#	Time	Username	Problem	Language	Result	Execution time	Memory
796905		Liudas	Traffic (IOI10_traffic)	C++17	100 / 100	907 ms	168524 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
void dfs(int head, int par, vector<int> &maxi, vector<int> &total, vector<vector<int>> &tree, int s){
    for(int i : tree[head]){
        if(i != par){
            dfs(i, head, maxi, total, tree, s);
            total[head] += total[i];
            maxi[head] = max(maxi[head], total[i]);
        }
    }
    maxi[head] = max(maxi[head], s - total[head]);
}
int LocateCentre(int N, int P[], int S[], int D[]){
    vector<vector<int>> tree(N);
    for(int i = 0; i < N-1; i ++){
        tree[S[i]].push_back(D[i]);
        tree[D[i]].push_back(S[i]);
    }
    vector<int> maxi(N), total(N);
    int s = 0;
    for(int i = 0; i < N; i ++){
        total[i] = P[i];
        s += P[i];
    }
    dfs(0, -1, maxi, total, tree, s);
    int ans = 2e9, id = -1;
    for(int i = 0; i < N; i ++){
        if(ans > maxi[i]){
            ans = maxi[i];
            id = i;
        }
    }
    return id;
}

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