제출 #536262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536262		timreizin	Traffic (IOI10_traffic)	C++17	100 / 100	1328 ms	158944 KiB

traffic

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

using namespace std;

using ll = long long;

int LocateCentre(int n,  int P[], int S[], int D[])
{
    vector<ll> val(n);
    for (int i = 0; i < n; ++i) val[i] = P[i];
    vector<vector<int>> adj(n);
    for (int i = 0; i + 1 < n; ++i)
    {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    vector<ll> dp = val;
    auto dfs1 = [&dp, &adj](auto self, int v, int p) -> ll
    {
        for (int u : adj[v]) if (u != p) dp[v] += self(self, u, v);
        return dp[v];
    };
    dfs1(dfs1, 0, -1);
    auto dfs2 = [&dp, &adj, &val](auto self, int v, int p, ll dpP) -> pair<ll, int>
    {
        pair<ll, int> res{dpP, v};
        dpP += val[v];
        for (int u : adj[v]) if (u != p)
        {
            res.first= max(res.first, dp[u]);
            dpP += dp[u];
        }
        for (int u : adj[v]) if (u != p)
        {
            pair<ll, int> ret = self(self, u, v, dpP - dp[u]);
            if (ret.first < res.first) res = ret;
        }
        return res;
    };
    return dfs2(dfs2, 0, -1, 0).second;
}

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