제출 #330521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330521		nicolaee3	Traffic (IOI10_traffic)	C++14	100 / 100	1380 ms	176236 KiB

traffic

#include<bits/stdc++.h>

using namespace std;

ifstream fin("milkvisits.in");
ofstream fout("milkvisits.out");
#define NMAX 1000005

typedef long long ll;
vector<int> v[NMAX];
ll val[NMAX];
ll P[NMAX];
ll minim = (1<<30);
int res;

void dfs(int nod,int tata)
{
    val[nod] = P[nod];
    for(auto u : v[nod])
    {
        if(u != tata)
        {
            dfs(u,nod);
            val[nod] += val[u];
        }
    }
}

void dfs2(int nod,int tata)
{
    ll maxim = val[0] - val[nod];
    for(auto u : v[nod])
    {
        if(u != tata)
        {
            maxim = max(maxim,val[u]);
        }
    }
    //cout<<nod<<" "<<maxim<<endl;
    if(maxim < minim)
    {
        minim = maxim;
        res = nod;
    }
    for(auto u : v[nod])
    {
        if(u != tata)
        {
            dfs2(u,nod);
        }
    }
}

int LocateCentre(int n,int p[],int s[],int d[])
{
    for(int i=0;i<=n-2;i++)
    {

        int a = s[i];
        int b = d[i];
        v[a].push_back(b);
        v[b].push_back(a);

    }
    for(int i=0;i<=n-1;i++)
        P[i] = p[i];

    dfs(0,-1);
    dfs2(0,-1);
    return res;
}

/*
int main()
{
    int p[NMAX],s[NMAX],d[NMAX];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }

    for(int i=0;i<=n-2;i++)
    {
        int a,b;
        cin>>s[i]>>d[i];
    }

    cout<<LocateCentre(n,p,s,d);

}
*/

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