oj.uz

Submission #224425

# Submission time Handle Problem Language Result Execution time Memory
224425 2020-04-17T21:33:00 Z jhnah917 Traffic (IOI10_traffic) C++14
0 / 100
 18 ms 24064 KB 
#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

int n, sum;
int a[1010101];
int sz[1010101];
vector<int> g[1010101];
int cst[1010101];
int ans = -1;

void dfs(int v, int p = -1){
    sz[v] = a[v];
    for(auto i : g[v]) if(i ^ p){
        dfs(i, v); sz[v] += sz[i];
    }
}

void solve(int v, int p = -1){
    cst[v] = sum - sz[v];
    for(auto i : g[v]) if(i ^ p){
        cst[v] = max(cst[v], sz[i]);
        solve(i, v);
    }
    if(ans == -1 || cst[ans] > cst[v]) ans = v;
}

int LocateCentre(int N, int P[], int S[], int D[]){
    n = N;
    for(int i=1; i<=n; i++) a[i] = P[i-1], sum += a[i];
    for(int i=0; i<n-1; i++){
        int s = S[i], e = D[i];
        g[s].push_back(e); g[e].push_back(s);
    }
    dfs(1, -1); solve(1, -1);
    return ans - 1;
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 24064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 24064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 24064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 24064 KB Output isn't correct
2 Halted 0 ms 0 KB -