Submission #893072

#	Time	Username	Problem	Language	Result	Execution time	Memory
893072		LCJLY	Traffic (IOI10_traffic)	C++14	100 / 100	982 ms	194720 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long 
typedef pair<int,int>pii;

vector<int>adj[1000005];
int arr[1000005];
int d[1000005];
int storage[1000005];
int sz[1000005];

void dfs(int index, int par){
	sz[index]=arr[index];
	storage[index]=arr[index]*d[index];
	for(auto it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		dfs(it,index);
		sz[index]+=sz[it];
		storage[index]+=storage[it];
	}
}

int best=LONG_LONG_MAX;
int cur=0;

void dp(int index, int par, int val){
	if(storage[0]+val<best){
		best=storage[0]+val;
		cur=index;
	}
	
	for(auto it:adj[index]){
		if(it==par) continue;
		int next=sz[0]-2*sz[it]+val;
		dp(it,index,next);
	}
}

int32_t LocateCentre(int32_t N, int32_t pp[], int32_t S[], int32_t D[]) {
	for(int x=0;x<N-1;x++){
		adj[S[x]].push_back(D[x]);
		adj[D[x]].push_back(S[x]);
	}
	
	for(int x=0;x<N;x++) arr[x]=pp[x];
	
	dfs(0,-1);
	
	dp(0,-1,0);
	
	return cur;
}

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