Submission #733777

#	Time	Username	Problem	Language	Result	Execution time	Memory
733777		penguin133	Traffic (IOI10_traffic)	C++17	100 / 100	993 ms	178588 KiB

traffic

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

#include "traffic.h"
//#define int long long
typedef long long ll;
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll P[1000005], sz[1000005];
vector <int> adj[1000005];
pair<long long, int> ans = {1e18, 0};
ll sm;

void dfs(int x, int par){
	sz[x] = P[x];
	ll tmp = 0;
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
		sz[x] += sz[i];
		tmp = max(tmp, sz[i]);
	}
	tmp = max(tmp, sm - sz[x]);
	ans = min(ans, {tmp, x});
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   for(int i=0;i<N-1;i++){
	   adj[S[i]].push_back(D[i]);
	   adj[D[i]].push_back(S[i]);
   }
   for(int i=0;i<N;i++)P[i] = pp[i], sm += pp[i];
   dfs(0, -1);
   return ans.se;
}

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