oj.uz

Submission #1032559

# Submission time Handle Problem Language Result Execution time Memory
1032559 2024-07-24T02:49:02 Z ezzzay Traffic (IOI10_traffic) C++14
0 / 100
 3 ms 7512 KB 
#include "traffic.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
int pp[N],S[N],D[N];
vector<int>v[N];
int k=0;
int w[N];
int ans=INT_MAX;
int x=-1;
void fun(int a,int p){
    int h=0;
    for(auto b:v[a]){
        if(b==p)continue;
        fun(b,a);
        w[a]+=w[b];
    }
    for(auto b:v[a]){
        if(b==p)continue;
        h=max(h,w[b]);
    }
    w[a]+=pp[a];
    h=max(h,k-w[a]);
    if(ans>h){
        ans=h;
        x=a;
    }
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
    int n=N;
   for(int i=0;i<n-1;i++){
        v[S[i]].pb(D[i]);
        v[D[i]].pb(S[i]);
    }
    
    for(int i=0;i<n;i++){
        k+=pp[i];
    }
    
    fun(0,-1);
    return x;
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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