oj.uz

Submission #805289

# Submission time Handle Problem Language Result Execution time Memory
805289 2023-08-03T14:49:09 Z QwertyPi Traffic (IOI10_traffic) C++14
0 / 100
 11 ms 23764 KB 
#include "traffic.h"

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 11;
int p[N], sz[N];
vector<int> G[N];
 
void dfs(int v, int par = -1){
	for(auto i : G[v]){
		if(i != par){
			dfs(i, v);
			sz[v] += sz[i];
		}
	}
	sz[v] += p[v];
}
 
int centroid(int v, int par = -1){
	for(auto i : G[v]){
		if(i != par && sz[i] >= (sz[0] + 1) / 2){
			return centroid(i, v);
		}
	}
	return v;
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   for(int i = 0; i < N - 1; i++){
      G[S[i]].push_back(D[i]);
      G[D[i]].push_back(S[i]);
   }
   dfs(0); return centroid(0);
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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