제출 #851510

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851510		abcvuitunggio	Traffic (IOI10_traffic)	C++17	100 / 100	666 ms	170832 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> ke[1000001];
long long sz[1000001];
void dfs(int u, int p){
    for (int v:ke[u])
        if (v!=p){
            dfs(v,u);
            sz[u]+=sz[v];
        }
}
int centroid(int u, int p){
    for (int v:ke[u])
        if (v!=p&&sz[v]*2>sz[0])
            return centroid(v,u);
    return u;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    for (int i=0;i<N-1;i++){
        ke[S[i]].push_back(D[i]);
        ke[D[i]].push_back(S[i]);
    }
    for (int i=0;i<N;i++)
        sz[i]=pp[i];
    dfs(0,0);
    return centroid(0,0);
}

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