Submission #383895

#	Time	Username	Problem	Language	Result	Execution time	Memory
383895		MODDI	Traffic (IOI10_traffic)	C++14	100 / 100	1377 ms	156208 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define mp make_pair
#define pb push_back
using namespace std;
vi G[1000000], sum, arr;
bool vis[1000000];

static int N,P[1000000],S[1000000],D[1000000];
void dfs(int node){
	vis[node] = true;
	int cur = arr[node];
	for(auto next : G[node]){
		if(!vis[next]){
			dfs(next);
			cur += sum[next];
		}
	}
	sum[node] = cur;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
	for(int i = 0; i < N - 1; i++)
	{
		G[S[i]].pb(D[i]);
		G[D[i]].pb(S[i]);
	}
	sum.resize(N,0);
	arr.resize(N);
	for(int i = 0; i < N; i++)
		arr[i] = pp[i];
		
	int id = 0, best = 1e9;
	dfs(0);
//	for(int i = 0; i < N; i++)
//		cout<<sum[i]<<" ";
//	cout<<endl;
	queue<pii> q;
	q.push(mp(0, 0));
	memset(vis,false,sizeof(vis));
	vis[0] = true;
	while(!q.empty()){
		pii state = q.front(); q.pop();
		//cout<<state.first<<" "<<state.second<<endl;
		int cur_max = state.second, help = 0;
		for(auto next :G[state.first]){
			if(!vis[next]){
				//cout<<"Incomming to "<<state.first<<" with sum "<<sum[next]<<endl;
				cur_max = max(cur_max, sum[next]);
				help += sum[next];
			}
		}
		if(cur_max < best){
			id = state.first;
			best = cur_max;
		}
		for(auto next : G[state.first]){
			if(!vis[next]){
				vis[next] = true;
				int pass = arr[state.first] + state.second + help - sum[next];
				q.push(mp(next, pass));
			}
		}
	}
	/*for(int i = 0; i < N; i++){
		memset(vis,false,sizeof(vis));
		dfs(i);
		int cur_max = 0;
		for(auto next : G[i])
			cur_max = max(cur_max, sum[next]);
			
		if(cur_max < best)
			id = i, best = cur_max;
	}
	*/
	return id;
}
/*int main(){
   int i;
   scanf("%d",&N);
   for (i=0;i<N;i++) scanf("%d",&P[i]);
   for (i=0;i<N-1;i++) scanf("%d%d",&S[i],&D[i]);
   int r = LocateCentre(N,P,S,D);
   printf("%d\n",r);
   return 0;
}*/

Compilation message (stderr)

traffic.cpp:14:36: warning: 'D' defined but not used [-Wunused-variable]
   14 | static int N,P[1000000],S[1000000],D[1000000];
      |                                    ^
traffic.cpp:14:25: warning: 'S' defined but not used [-Wunused-variable]
   14 | static int N,P[1000000],S[1000000],D[1000000];
      |                         ^
traffic.cpp:14:14: warning: 'P' defined but not used [-Wunused-variable]
   14 | static int N,P[1000000],S[1000000],D[1000000];
      |              ^
traffic.cpp:14:12: warning: 'N' defined but not used [-Wunused-variable]
   14 | static int N,P[1000000],S[1000000],D[1000000];
      |            ^

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