제출 #964945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964945		Boomyday	Traffic (IOI10_traffic)	C++17	0 / 100	3 ms	4444 KiB

traffic

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

using ll = long long;

#include "traffic.h"





vector<ll> nums; vector<vector<int>> adj;

ll mn = 1e18;
ll ans = -1;
ll sm = 0;

void dfs(int u, int p=-1){
    ll msz = -1;

    for(auto& v:adj[u]){
        if (v != p){
            dfs(v,u);
            nums[u] += nums[v];
            msz = max(msz,nums[v]);

        }
    }
    msz = max(msz,sm-nums[u]);
    if (msz < mn){
        mn = msz; ans = u;
    }

}


int LocateCentre(int n, int p[], int s[], int d[]) {
    nums.resize(n); adj.resize(n);

    for(int i=0;i<n;++i){ nums[i] = p[i]; sm += nums[i];}
    for(int i=0;i<n;++i) {
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    dfs(0);

    return ans;

}

/*
static int N,P[1000000],S[1000000],D[1000000];

int main(){
    int i;
    scanf("%d",&N);
    for (i=0;i<N;i++) scanf("%d",&P[i]);
    for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
    int r = LocateCentre(N,P,S,D);
    printf("%d\n",r);
    return 0;
}*/

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