oj.uz

Submission #308282

# Submission time Handle Problem Language Result Execution time Memory
308282 2020-09-30T19:31:53 Z Temmie Traffic (IOI10_traffic) C++17
0 / 100
 0 ms 384 KB 
#include <bits/stdc++.h>

std::vector <std::vector <int>> g;
std::vector <int> ans, sms;
int sum = 0;

void dfs(int val[], int node = 0, int par = -1) {
	sms[node] = val[node];
	for (int x : g[node]) if (x != par) {
		dfs(val, node, x);
		sms[node] += sms[x];
		ans[node] = std::max(ans[node], sms[x]);
	}
	ans[node] = std::max(ans[node], sum - sms[node]);
}

int LocateCentre(int n, int val[], int u[], int v[]) {
	for (int i = 0; i < n; i++) sum += val[i];
	g.resize(n);
	ans.resize(n, 0);
	sms.resize(n, 0);
	for (int i = 0; i < n - 1; i++) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	dfs(val);
	int ansind = 0, best = INT_MAX;
	for (int i = 0; i < n; i++) {
		if (ans[i] < best) {
			best = ans[i];
			ansind = i;
		}
	}
	return ansind;
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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