Submission #1210667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210667		candi_ositos	Traffic (IOI10_traffic)	C++20	100 / 100	1285 ms	184296 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
/*
int LocateCentre(int N, int P[1000000], int S[1000000], int D[1000000]);
int main()
{
    static int N,P[1000000],S[1000000],D[1000000];
    int i;
    cin>>N;
    for (i=0;i<N;i++)
    {
        cin>>P[i];
    }
    for (i=0;i<N-1;i++)
    {
        cin>>S[i]>>D[i];
    }
    cout<<LocateCentre(N,P,S,D)<<"\n";
    return 0;
}
*/
vector <int> p;
vector <int> a;
vector <int> b;
vector <int> s;
vector <long long int> tn, tt;
vector <set <int> > son;
int n;
long long int mt;
void mr(int i)
{
    if(p[p[i]]==p[i])
    {
        son[p[i]].erase(i);
        son[i].insert(p[i]);
        p[p[i]]=i;
        return;
    }
    mr(p[i]);
    son[p[i]].erase(i);
    son[i].insert(p[i]);
    p[p[i]]=i;
    return;
}
int floodfill(int i)
{
    tt[i]=s[i];
    for(auto j: son[i])
    {
        long long int aux=floodfill(j);
        tt[i]+=aux;
        if(aux>tn[i])
        {
            tn[i]=aux;
        }
    }
    return tt[i];
}
int LocateCentre(int N, int P[1000000], int S[1000000], int D[1000000])
{
    n=N;
    p.resize(n);
    a.resize(n);
    b.resize(n);
    s.resize(n);
    son.resize(n);
    tn.assign(n, 0);
    tt.assign(n, 0);
    p[0]=0;
    s[0]=P[0];
    for(int i=0; i<n-1; ++i)
    {
        p[i+1]=i+1;
        a[i]=S[i];
        b[i]=D[i];
        s[i+1]=P[i+1];
    }
    for(int i=0; i<n-1; ++i)
    {
        if(p[a[i]]==a[i])
        {
            p[a[i]]=b[i];
            son[b[i]].insert(a[i]);
        }
        else if(p[b[i]]==b[i])
        {
            p[b[i]]=a[i];
            son[a[i]].insert(b[i]);
        }
        else
        {
            mr(a[i]);
            son[p[a[i]]].erase(a[i]);
            p[a[i]]=b[i];
            son[b[i]].insert(a[i]);
        }
    }
    int trp=0;
    while(p[trp]!=trp)
    {
        trp=p[trp];
    }
    long long int mt=floodfill(trp);
    long long int mit=mt;
    int ar=-1;
    for(int i=0; i<n; ++i)
    {
        long long int aux=tn[i];
        if(mt-tt[i]>tn[i])
        {
            aux=mt-tt[i];
        }
        if(aux<mit)
        {
            mit=aux;
            ar=i;
        }
    }
    return ar;
}

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