Submission #1113520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113520		Zflop	Traffic (IOI10_traffic)	C++14	0 / 100	5 ms	33104 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
const int NMAX = (int)1e6 + 1;
vector<int>ad[NMAX];
int sum[NMAX],A[NMAX],ans = (int)1e9;
void dfs(int node,int parent) {
	for (auto& x : ad[node])
		if (x != parent) {
			dfs(x,node); 
			sum[node] += sum[x];
			}
	}

void dfs1(int node,int parent,int sus) {
	int cost = sus;
	for (auto& x : ad[node])
		if (x != parent) 
			cost += sum[x];
	ans = min(ans,cost);
	for (auto& x : ad[node])
		if (x != parent)
			dfs1(x,node,cost - sum[x] + A[x]);
	}

int LocateCentre(int N,int P[],int S[],int D[]) {
	for (int i = 0; i < N;++i) 
		sum[i] = A[i] = P[i];
	for (int i = 0; i < N - 1;++i) {
		ad[S[i]].push_back(D[i]);
		ad[D[i]].push_back(S[i]);
		}
	dfs(0,0);
	dfs1(0,0,0);
	return ans;
	}

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