Submission #426585

#	Time	Username	Problem	Language	Result	Execution time	Memory
426585		snasibov05	Traffic (IOI10_traffic)	C++14	100 / 100	1547 ms	155048 KiB

traffic

#include "traffic.h"
#include <vector>

using namespace std;

#define pb push_back
#define oo 1000000000

vector<vector<int>> ed;
vector<int> subtr;
vector<int> res;

int sum = 0;

void calcSubtreeSum(int v, int pr){
    for (auto to : ed[v]){
        if (to == pr) continue;
        calcSubtreeSum(to, v);
        subtr[v] += subtr[to];
    }
}

void dfs(int v, int pr){
    if (pr != -1) res[v] = sum - subtr[v];

    for (auto to : ed[v]){
        if (to == pr) continue;
        res[v] = max(res[v], subtr[to]);
        dfs(to, v);
    }
}

int LocateCentre(int n, int pp[], int s[], int d[]) {

    ed.resize(n);
    subtr.resize(n);
    res.resize(n);

    for (int i = 0; i < n; ++i) {
        subtr[i] += pp[i];
        sum += pp[i];
    }

    for (int i = 0; i < n-1; ++i){
        ed[s[i]].pb(d[i]);
        ed[d[i]].pb(s[i]);
    }

    calcSubtreeSum(0, -1);
    dfs(0, -1);

    int mn = oo * 2;
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        if (res[i] < mn) mn = res[i], ans = i;
    }

    return ans;

}

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