Submission #729258

#	Time	Username	Problem	Language	Result	Execution time	Memory
729258		NintsiChkhaidze	Traffic (IOI10_traffic)	C++17	100 / 100	972 ms	186404 KiB

traffic

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#include "traffic.h"
using namespace std;

ll tot,dp[1000005],ansval;
int ans;
vector <int> v[1000005];
void dfs(int x,int par){
	ll r=0,sum=0;
	for (int to: v[x]){
		if (to==par) continue;
		dfs(to,x);
		r=max(r,dp[to]);
		sum += dp[to];
	}
	
	r=max(r,tot - dp[x] - sum);
	dp[x]+= sum;
	if (r < ansval) ansval = r,ans = x;
}
int LocateCentre(int n, int p[], int S[], int D[]) {
	ans=0;
	ansval = 1e18;
    for (int i=0;i<n;i++)
    	tot += p[i],dp[i] = p[i];
    	
    for (int i = 0; i < n - 1; i++){
		v[S[i]].pb(D[i]);
		v[D[i]].pb(S[i]);
    }
    dfs(0,0);
    
    for (int i=0;i<n;i++) v[i].clear(),dp[i]=0;
    return ans;
}

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