Submission #466694

#	Time	Username	Problem	Language	Result	Execution time	Memory
466694		eddieee	Traffic (IOI10_traffic)	C++17	100 / 100	1315 ms	155196 KiB

traffic

#include<bits/stdc++.h>
#include<traffic.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

const int MAXN=1e6+5;
int INF=INT_MAX;

int n;
int val[MAXN];
vector<int> adj[MAXN];
int ans;
int sz[MAXN];

inline void comp(int u,int par=-1){
    sz[u]=val[u];
    for(auto &v:adj[u])if(v!=par){
        comp(v,u);
        sz[u]+=sz[v];
    }
}

inline void dfs(int u,int x=0,int par=-1){
    int mx=x;
    for(auto &v:adj[u]) if(v!=par){
        dfs(v,x+sz[u]-sz[v],u);
        mx=max(mx,sz[v]);
    }
    if(mx<INF){
        INF=mx;
        ans=u;
    }
}

int LocateCentre(int n,int p[],int d[],int s[]){
    for(int i=0;i<n;++i){
        val[i]=p[i];
    }
    for(int i=0;i<n-1;++i){
        adj[s[i]].push_back(d[i]);
        adj[d[i]].push_back(s[i]);
    }
    comp(0);
    dfs(0);
    return ans;
}

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