제출 #961754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961754		hirayuu_oj	Traffic (IOI10_traffic)	C++17	100 / 100	889 ms	166992 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define all(x) x.begin(),x.end()
using ll=long long;
const ll INF=(1LL<<60)-1;

void dfs(int pos,int bef,vector<vector<int>> &gr,vector<int> &p){
    for(int i:gr[pos]){
        if(i!=bef){
            dfs(i,pos,gr,p);
            p[pos]+=p[i];
        }
    }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    vector<vector<int>> gr(N);
    rep(i,N-1){
        gr[S[i]].push_back(D[i]);
        gr[D[i]].push_back(S[i]);
    }
    vector<int> p(N);
    rep(i,N){
        p[i]=pp[i];
    }
    dfs(0,-1,gr,p);
    int ans=-1;
    ll cst=INF;
    rep(i,N){
        ll now=p[0]-p[i];
        for(int j:gr[i]){
            if(p[i]>=p[j]){
                now=max(now,(ll)p[j]);
            }
        }
        if(cst>now){
            cst=now;
            ans=i;
        }
    }
    return ans;
}

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