Submission #1172502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172502		AlgorithmWarrior	Traffic (IOI10_traffic)	C++20	100 / 100	446 ms	133472 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"

using namespace std;

static int N,P[1000000],S[1000000],D[1000000];
vector<int>tree[1000000];
int subsz[1000000];

int get_subsz(int nod,int tata,int pp[]){
    subsz[nod]=pp[nod];
    for(auto fiu : tree[nod])
        if(fiu!=tata)
            subsz[nod]+=get_subsz(fiu,nod,pp);
    return subsz[nod];
}

void add_edge(int u,int v){
    tree[u].push_back(v);
    tree[v].push_back(u);
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
    int i;
    for(i=0;i<N-1;++i)
        add_edge(S[i],D[i]);
    get_subsz(0,-1,pp);
    int raspnod=-1;
    int raspsz=2e9+1;
    for(i=0;i<N;++i){
        int maxim=0;
        for(auto fiu : tree[i])
            if(subsz[i]>subsz[fiu] && maxim<subsz[fiu])
                maxim=subsz[fiu];
        if(maxim<subsz[0]-subsz[i])
            maxim=subsz[0]-subsz[i];
        if(raspsz>maxim){
            raspsz=maxim;
            raspnod=i;
        }
    }
    return raspnod;
}

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