Submission #234562

#	Time	Username	Problem	Language	Result	Execution time	Memory
234562		triple_fault	Traffic (IOI10_traffic)	C++14	100 / 100	1633 ms	163064 KiB

traffic

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

#define ll long long
#define MAX 1000000

using namespace std;

ll n;
vector<vector<ll>> adj_list(MAX, vector<ll>{});
ll vals[MAX];
ll dp[MAX];

void dfs_cnt(ll idx, ll parent = -1) {
    dp[idx] = vals[idx];
    for (auto &each: adj_list[idx]) {
        if (each == parent) continue;
        dfs_cnt(each, idx);
        dp[idx] += dp[each];
    }
}

ll mx(vector<ll> tc) {
    ll ret = 0;
    for (auto &each: tc) ret = max(ret, each);
    return ret;
}

ll calc(ll idx) {
    vector<ll> ret;
    for (auto &each: adj_list[idx]) ret.push_back(dp[each]);
    return mx(ret);
}

/* cnt, node */
pair<ll, ll> foo(ll idx, ll parent = -1) {
    pair<ll, ll> ret = {calc(idx), idx};

    for (auto &each: adj_list[idx]) {
        if (each == parent) continue;

        dp[idx] -= dp[each];
        dp[each] += dp[idx];
        pair<ll, ll> pos = foo(each, idx);
        if (pos.first < ret.first) ret = pos;
        dp[each] -= dp[idx];
        dp[idx] += dp[each];
    }
    return ret;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    n = (ll)N;
    for (ll i = 0; i < n; ++i) vals[i] = (ll)pp[i];
    for (ll i = 0; i < (n - 1); ++i) {
        ll x = S[i], y = D[i];
        adj_list[x].push_back(y);
        adj_list[y].push_back(x);
    }
    memset(dp, 0, sizeof dp);
    dfs_cnt(0);
    pair<ll, ll> ans = foo(0);
    return ans.second;
}

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