Submission #502552

#	Time	Username	Problem	Language	Result	Execution time	Memory
502552		Fake4Fun	Traffic (IOI10_traffic)	C++14	100 / 100	935 ms	174628 KiB

traffic

// source: https://oj.uz/problem/view/IOI10_traffic

#include "traffic.h"
#include<iostream>
#include<vector>
using namespace std;
const int N=1e6+5;
int n,p[N];
int t1[N],dad[N];
vector<int> adj[N];
void DFS(int pre,int u){
    t1[u]=p[u];
    dad[u]=pre;
    for(auto i:adj[u]){
        if(i==pre) continue;
        DFS(u,i);
        t1[u]+=t1[i];
    }
}
int LocateCentre(int Xn,int Xp[],int U[],int V[]){
    n=Xn;
    for(int i=0;i<n-1;i++){
        adj[U[i]].push_back(V[i]);
        adj[V[i]].push_back(U[i]);
    }
    for(int i=0;i<n;i++) p[i]=Xp[i];
    DFS(-1,0);
    int all=t1[0];
    int mi, pos=-1;
    for(int u=0;u<n;u++){
        int val=all-t1[u];
        for(auto i:adj[u]){
            if(i==dad[u]) continue;
            val=max(val,t1[i]);
        }
        if(pos==-1||mi>val) pos=u, mi=val;
    }
    return pos;
}

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