Submission #1032567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032567		ezzzay	Traffic (IOI10_traffic)	C++14	100 / 100	617 ms	217716 KiB

traffic

#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e6+5;
vector<int>v[N];
int k=0;
int w[N];
int P[N];
int ans=INT_MAX;
int x=-1;
void fun(int a,int p){
    int h=0;
    for(auto b:v[a]){
        if(b==p)continue;
        fun(b,a);
        w[a]+=w[b];
    }
    for(auto b:v[a]){
        if(b==p)continue;
        h=max(h,w[b]);
    }
    w[a]+=P[a];
    h=max(h,k-w[a]);
    if(ans>h){
        ans=h;
        x=a;
    }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    int n=N;
    for(int i=0;i<n;i++){
        w[i]=0;
        P[i]=pp[i];
    }
   for(int i=0;i<n-1;i++){
        v[S[i]].pb(D[i]);
        v[D[i]].pb(S[i]);
    }
    
    for(int i=0;i<n;i++){
        k+=pp[i];
    }
    
    fun(0,-1);
    return x;
}

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