Submission #522394

#	Time	Username	Problem	Language	Result	Execution time	Memory
522394		new_acc	Traffic (IOI10_traffic)	C++14	0 / 100	12 ms	23816 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){
	int maxi=nad;
	for(auto u:graf[v]){
		if(u==o) continue;
		maxi=max(maxi,pod[u]);
	}
	if(res>maxi) res=maxi,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;
}
/*int main(){
	int p[5],s[4],d[4];
	int n=5;
	s[0]=0,d[0]=2,s[1]=1,d[1]=2,s[2]=2,d[2]=3,s[3]=3,d[3]=4;
	p[0]=10,p[1]=10,p[2]=10,p[3]=20,p[4]=20;
	cout<<LocateCentre(n,p,s,d)<<"\n";
}*/

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