oj.uz

Submission #356847

# Submission time Handle Problem Language Result Execution time Memory
356847 2021-01-23T23:33:54 Z penguinhacker Traffic (IOI10_traffic) C++14
0 / 100
 2 ms 2668 KB 
// source: https://oj.uz/problem/view/IOI10_traffic
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 100000;
int n, ans, a[mxN], sz[mxN], mx[mxN];
vector<int> adj[mxN];

void dfs(int u = 0, int p = -1) {
	sz[u] = a[u];
	mx[u] = 0;
	for (int v : adj[u]) if (v != p) {
		dfs(v, u);
		sz[u] += sz[v];
		mx[u] = max(mx[u], sz[v]);
	}
}

void dfs2(int u = 0, int p = -1) {
	if (ans == -1 || mx[u] < mx[ans]) ans = u;
	for (int v : adj[u]) if (v != p) {
		mx[v] = max(mx[v], mx[0] - mx[v]);
		dfs2(v, u);
	}
}

int LocateCentre(int _n, int p[], int s[], int d[]) {
	n = _n;
	for (int i = 0; i < n; ++i) a[i] = p[i];
	for (int i = 0; i < n - 1; ++i) {
		adj[s[i]].push_back(d[i]);
		adj[d[i]].push_back(s[i]);
	}
	ans = -1;
	dfs();
	dfs2();
	return ans;
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	return 0;
}*/

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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