Submission #362400

#	Time	Username	Problem	Language	Result	Execution time	Memory
362400		wind_reaper	Traffic (IOI10_traffic)	C++17	100 / 100	1180 ms	170892 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> adj;
vector<int64_t> cur, child, mx; 
int64_t fans = 0; 

void dfs(int node, int par){
	for(int v : adj[node]){
		if(v == par)
			continue;
		dfs(v, node);
		mx[node] = max(mx[node], child[v]);
		child[node] += child[v];
	}
	mx[node] = max(mx[node], fans - child[node] - cur[node]);
	child[node] += cur[node]; 
}
int LocateCentre(int n, int p[], int s[], int d[]){
	adj.resize(n); 
	cur.resize(n); 
	child.resize(n); 
	mx.resize(n);
	for(int i = 0; i < n - 1; i++){
		adj[s[i]].push_back(d[i]);
		adj[d[i]].push_back(s[i]);
	}

	for(int i = 0; i < n; i++){
		cur[i] = p[i];
		fans += p[i];
	}

	dfs(0, 0);

	return min_element(mx.begin(), mx.end()) - mx.begin();
}	

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