제출 #595656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
595656		Bench0310	Traffic (IOI10_traffic)	C++17	100 / 100	1055 ms	208344 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"

using namespace std;
typedef long long ll;

int LocateCentre(int n,int x[],int va[],int vb[])
{
    vector<int> v[n];
    for(int i=0;i<n-1;i++)
    {
        v[va[i]].push_back(vb[i]);
        v[vb[i]].push_back(va[i]);
    }
    int sum=0;
    for(int i=0;i<n;i++) sum+=x[i];
    vector<int> s(n,0);
    array<int,2> res={2000000001,0};
    function<void(int,int)> dfs=[&](int a,int p)
    {
        s[a]=x[a];
        int mx=0;
        for(int to:v[a])
        {
            if(to==p) continue;
            dfs(to,a);
            s[a]+=s[to];
            mx=max(mx,s[to]);
        }
        mx=max(mx,sum-s[a]);
        res=min(res,{mx,a});
    };
    dfs(0,-1);
    return res[1];
}

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