Submission #730739

# Submission time Handle Problem Language Result Execution time Memory
730739 2023-04-26T10:50:33 Z Jarif_Rahman Traffic (IOI10_traffic) C++17
0 / 100
1 ms 212 KB
#include "traffic.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int n, sum = 0;
vector<vector<int>> tree;
vector<int> P, PP;
int mn = 2e9+1, ans = -1;

void dfs(int nd, int ss){
    int mx = 0, up = sum;
    for(int x: tree[nd]) if(x != ss) dfs(x, nd), PP[nd]+=PP[x], mx = max(mx, PP[x]), up-=PP[x];
    mx = max(mx, up);
    if(mx < mn) mn = mx, ans = nd;
}

int LocateCentre(int _n, int _P[], int U[], int V[]){
    swap(n, _n);
    tree.resize(n);
    P.resize(n);
    for(int i = 0; i < n; i++) P[i] = _P[i];
    PP = P;
    for(int i = 0; i < n-1; i++){
        tree[U[i]].pb(V[i]);
        tree[V[i]].pb(U[i]);
    }
    for(int x: P) sum+=x;
    dfs(0, -1);
    return ans;
}
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -