Submission #1004081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004081		overwatch9	Traffic (IOI10_traffic)	C++17	100 / 100	722 ms	171092 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <int>> adj;
vector <int> st_sz;
vector <int> depth;
int ans = 0;
void dfs(int s, int p, int d) {
	depth[s] = d;
   	for (auto i : adj[s]) {
		if (i == p)
			continue;
		dfs(i, s, d+1);
		st_sz[s] += st_sz[i];
		if (s == 1)
			ans = max(ans, st_sz[i]);
	}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
   adj.resize(N+1);
   depth = st_sz = vector <int> (N+1);
   for (int i = 0; i < N-1; i++) {
      S[i]++;
      D[i]++;
      adj[S[i]].push_back(D[i]);
      adj[D[i]].push_back(S[i]);
   }
	for (int i = 1; i <= N; i++)
		st_sz[i] = pp[i-1];
	dfs(1, 1, 0);
	int node = 1;
	for (int i = 2; i <= N; i++) {
		int tp = 0;
		for (auto j : adj[i]) {
			if (depth[j] > depth[i])
				tp = max(tp, st_sz[j]);
			else
				tp = max(tp, st_sz[1] - st_sz[i]);
		}
		if (ans > tp) {
			ans = tp;
			node = i;
		}
	}
	return node-1;
}
// int main() {
// 	int n;
// 	int pp[n], s[n], d[n];
// 	cin >> n;
// 	for (int i = 0; i < n; i++)
// 		cin >> pp[i];
// 	for (int i = 0; i < n-1; i++)
// 		cin >> s[i] >> d[i];
// 	cout << LocateCentre(n, pp, s, d) << '\n';
// }

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25