Submission #522393

#	Time	Username	Problem	Language	Result	Execution time	Memory
522393		new_acc	Traffic (IOI10_traffic)	C++14	0 / 100	12 ms	23792 KiB

traffic

#include<bits/stdc++.h>
#define fi first
#define se second
#define rep(a, b) for(int a = 0; a < (int)(b); a++)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
vi graf[N];
int pod[N],t[N];
ll res=LLONG_MAX;
int g;
void dfs(int v,int o){
	pod[v]+=t[v];
	for(auto u:graf[v]){
		if(u==o) continue;
		dfs(u,v);
		pod[v]+=pod[u];
	}
}
void dfs2(int v,int o,int nad){
	if(res>pod[v]+nad) res=pod[v]+nad,g=v;
	for(auto u:graf[v]){
		if(u==o) continue;
		dfs2(u,v,pod[v]-pod[u]);
	}
}
int LocateCentre(int n,int p[],int s[],int d[]){
	rep(i,n-1) graf[s[i]].push_back(d[i]),graf[d[i]].push_back(s[i]);
	rep(i,n) t[i]=p[i];
	dfs(0,0);
	dfs2(0,0,0);
	return g;
}

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