Submission #508815

#	Time	Username	Problem	Language	Result	Execution time	Memory
508815		tabr	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	332 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int LocateCentre(int n, int* a, int* e1, int* e2) {
    vector<vector<int>> g(n);
    for (int i = 0; i < n - 1; i++) {
        e1[i]--;
        e2[i]--;
        g[e1[i]].emplace_back(e2[i]);
        g[e2[i]].emplace_back(e1[i]);
    }
    function<void(int, int)> dfs = [&](int v, int p) {
        for (int to : g[v]) {
            if (to == p) {
                continue;
            }
            dfs(to, v);
            a[v] += a[to];
        }
    };
    dfs(0, -1);
    int ans = -1;
    int sum = (int) 2e9 + 10;
    function<void(int, int)> reroot = [&](int v, int p) {
        int mx = -1;
        for (int to : g[v]) {
            mx = max(mx, a[to]);
        }
        if (mx < sum) {
            sum = mx;
            ans = v;
        }
        for (int to : g[v]) {
            if (to == p) {
                continue;
            }
            int qv = a[v];
            int qto = a[to];
            a[v] = qv - qto;
            a[to] = qv;
            reroot(to, v);
            a[v] = qv;
            a[to] = qto;
        }
    };
    reroot(0, -1);
    ans++;
    return ans;
}

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