Submission #493023

#	Time	Username	Problem	Language	Result	Execution time	Memory
493023		JooDdae	Traffic (IOI10_traffic)	C++17	100 / 100	1122 ms	162792 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
using ll = long long;

vector<int> v[1001001];
ll sum, sz[1001001], c[1001001];

int dfs(int u, int p){
    sz[u] = c[u];
    for(auto x : v[u]) if(x != p) sz[u] += dfs(x, u);
    return sz[u];
}

pair<ll, int> dfs2(int u, int p){
    pair<ll, int> re = {sum-sz[u], u};
    for(auto x : v[u]) if(x != p) re.first = max(re.first, sz[x]);
    for(auto x : v[u]) if(x != p) re = min(re, dfs2(x, u));
    return re;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    for(int i=0;i<N-1;i++) v[S[i]].push_back(D[i]), v[D[i]].push_back(S[i]);
    for(int i=0;i<N;i++) c[i] = pp[i], sum += pp[i];
    dfs(0, 0);
    return dfs2(0, 0).second;
}

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