제출 #641987

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
641987		PoonYaPat	Traffic (IOI10_traffic)	C++14	100 / 100	887 ms	155080 KiB

traffic

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

int n,ans_node;
ll sum,ans=4e18,p[1000001];
vector<int> adj[1000001];

ll dfs(int x, int par) {
    ll cnt=p[x],mmax=0;

    for (auto s : adj[x]) {
        if (s==par) continue;
        ll cnt_child=dfs(s,x);
        cnt+=cnt_child;
        mmax=max(mmax,cnt_child);
    }
    mmax=max(mmax,sum-cnt);
    if (mmax<ans) {
        ans=mmax;
        ans_node=x;
    }
    return cnt;
}

int LocateCentre(int N, int P[], int S[], int D[]) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        adj[S[i]].push_back(D[i]);
        adj[D[i]].push_back(S[i]);
    }
    for (int i=0; i<n; ++i) sum+=P[i],p[i]=P[i];
    dfs(0,0);
    return ans_node;
}

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