제출 #271913

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
271913		TMJN	Traffic (IOI10_traffic)	C++17	0 / 100	16 ms	23808 KiB

traffic

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

vector<int>v[1000000];
long long c[1000000],m[1000000];

void dfs(int x,int from){
	for(int i:v[x]){
		if(i==from)continue;
		dfs(i,x);
		c[x]+=c[i];
	}
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	for(int i=0;i<N-1;i++){
		v[S[i]].push_back(D[i]);
		v[D[i]].push_back(S[i]);
	}
	for(int i=0;i<N;i++){
		c[i]=pp[i];
	}
	dfs(0,0);
	for(int i=0;i<N-1;i++){
		m[S[i]]=max(m[S[i]],abs(c[S[i]]-c[D[i]]));
		m[D[i]]=max(m[D[i]],abs(c[S[i]]-c[D[i]]));
	}
	pair<long long,int>res={0xE869120E869120,-1};
	for(int i=0;i<N;i++){
		res=min(res,{m[i],i});
	}
	return res.second;
}

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