제출 #936236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
936236		Warinchai	Traffic (IOI10_traffic)	C++14	100 / 100	827 ms	174816 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>v[1000005];
int cost[1000005];
int mxc[1000005];
int ppl[1000005];
void dfs(int u,int p=-1){
    //cerr<<u<<"\n";
    for(auto x:v[u])if(x!=p){
        dfs(x,u);
        cost[u]+=cost[x]+ppl[x];
        mxc[u]=max(cost[x]+ppl[x],mxc[u]);
    }
}
int centroid(int u,int val=0,int p=-1){
    //cerr<<u<<" "<<val<<"\n";
    int sum=val;
    for(auto x:v[u])if(x!=p)sum+=cost[x]+ppl[x];
    //for(auto x:v[u])if(x!=p)cerr<<cost[x]<<" "<<ppl[x]<<"\n";
    //cerr<<sum<<"\n";
    for(auto x:v[u])if(x!=p){
        if(max(val,mxc[u])>max(sum-cost[x]-ppl[x]+ppl[u],mxc[x]))return centroid(x,sum-cost[x]-ppl[x]+ppl[u],u);
    }
    return u;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    for(int i=0;i<N;i++)ppl[i]=pp[i];
    for(int i=0;i<N-1;i++)v[S[i]].push_back(D[i]),v[D[i]].push_back(S[i]);
    dfs(0);
    //for(int i=0;i<N;i++)cerr<<cost[i]<<"\n";
    return centroid(0);
}

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