Submission #224426

#	Time	Username	Problem	Language	Result	Execution time	Memory
224426		jhnah917	Traffic (IOI10_traffic)	C++14	100 / 100	1342 ms	159476 KiB

traffic

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

int n, sum;
int a[1010101];
int sz[1010101];
vector<int> g[1010101];
int cst[1010101];
int ans = -1;

void dfs(int v, int p = -1){
    sz[v] = a[v];
    for(auto i : g[v]) if(i ^ p){
        dfs(i, v); sz[v] += sz[i];
    }
}

void solve(int v, int p = -1){
    cst[v] = sum - sz[v];
    for(auto i : g[v]) if(i ^ p){
        cst[v] = max(cst[v], sz[i]);
        solve(i, v);
    }
    if(ans == -1 || cst[ans] > cst[v]) ans = v;
}

int LocateCentre(int N, int P[], int S[], int D[]){
    n = N;
    for(int i=1; i<=n; i++) a[i] = P[i-1], sum += a[i];
    for(int i=0; i<n-1; i++){
        int s = S[i] + 1, e = D[i] + 1;
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs(1, -1); solve(1, -1);
    return ans - 1;
}

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