Submission #270273

#	Time	Username	Problem	Language	Result	Execution time	Memory
270273		shinjan	Traffic (IOI10_traffic)	C++14	100 / 100	1477 ms	155220 KiB

traffic

#include <iostream>
#include <bits/stdc++.h>
#define maxN 1000001
using namespace std;
vector<int> drvo[maxN];
int subtree[maxN];
int fans[maxN];
pair<int,int> ans={-1,INT_MAX};
int dfs(int v,int par)
{
    int sz=fans[v];
    for(int x:drvo[v])
    {
        if(x!=par)
        {
            sz+=dfs(x,v);
        }
    }
    subtree[v]=sz;
    return sz;
}
void reshi(int v,int par)
{
    int lokal=0;
    if(par!=-1)
    {
        lokal=subtree[0]-subtree[v];
    }
    for(int x:drvo[v])
    {
        if(x!=par)
        {
            lokal=max(lokal,subtree[x]);
        }
    }
    if(lokal<ans.second)
    {
        ans.second=lokal;
        ans.first=v;
    }
    for(int x:drvo[v])
    {
        if(x!=par)
        {
            reshi(x,v);
        }
    }
}
int LocateCentre(int n,int p[],int s[],int d[])
{
    for(int i=0;i<n-1;i++)
    {
        drvo[s[i]].push_back(d[i]);
        drvo[d[i]].push_back(s[i]);
    }
    for(int i=0;i<n;i++)
    {
        fans[i]=p[i];
    }
    dfs(0,-1);
    reshi(0,-1);
    return ans.first;
}

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