Submission #440685

#	Time	Username	Problem	Language	Result	Execution time	Memory
440685		FEDIKUS	Traffic (IOI10_traffic)	C++17	100 / 100	1685 ms	152708 KiB

traffic

#include "traffic.h"

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+10;

vector<int> g[maxn];
vector<int> klk(maxn);
vector<int> tren(maxn);

void dfs1(int cvor,int prosli=-1){
    tren[cvor]=klk[cvor];
    for(int i:g[cvor]){
        if(i==prosli) continue;
        dfs1(i,cvor);
        tren[cvor]+=tren[i];
    }
}

pair<int,int> dfs2(int cvor,int prosli=0){
    pair<int,int> ovde={-1,cvor};
    if(cvor!=prosli){
        tren[prosli]-=tren[cvor];
        tren[cvor]+=tren[prosli];
    }
    for(int i:g[cvor]) ovde=max(ovde,make_pair(tren[i],cvor));
    for(int i:g[cvor]){
        if(i==prosli) continue;
        ovde=min(ovde,dfs2(i,cvor));
    }
    if(cvor!=prosli){
        tren[cvor]-=tren[prosli];
        tren[prosli]+=tren[cvor];
    }
    return ovde;
}

int LocateCentre(int n, int pp[], int s[], int d[]) {
    for(int i=0;i<n;i++){
        klk[i]=pp[i];
        if(i<n-1){
            g[s[i]].push_back(d[i]);
            g[d[i]].push_back(s[i]);
        }
    }
    dfs1(0);
    return dfs2(0).second;
}

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