oj.uz

Submission #330510

# Submission time Handle Problem Language Result Execution time Memory
330510 2020-11-25T15:15:45 Z nicolaee3 Traffic (IOI10_traffic) C++14
0 / 100
 16 ms 23788 KB 
#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);

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;
    minim = min(minim,maxim);
    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 minim;
}

/*
int main()
{
    ll 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);

}

5
10 10 10 20 20
0 2
1 2
2 3
3 4

*/

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Incorrect 15 ms 23788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Incorrect 15 ms 23788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Incorrect 15 ms 23788 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Incorrect 15 ms 23788 KB Output isn't correct
3 Halted 0 ms 0 KB -