oj.uz

Submission #362399

# Submission time Handle Problem Language Result Execution time Memory
362399 2021-02-03T04:52:01 Z wind_reaper Traffic (IOI10_traffic) C++17
0 / 100
 1 ms 364 KB 
#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 max_element(mx.begin(), mx.end()) - mx.begin();
}

Subtask #1
0 / 25.0

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

Subtask #2
0 / 25.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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