Submission #426665

#	Time	Username	Problem	Language	Result	Execution time	Memory
426665		nots0fast	Traffic (IOI10_traffic)	C++17	100 / 100	1376 ms	137324 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp(a) setprecision(a)<<fixed
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define MAX (int)(pow(10,6) + 10)
#define pb(a) push_back(a)
const ll INF = 0x3f3f3f3f;
const ll inf = pow(10,18);
ll modulo = pow(10,9) + 7;

ll dp[MAX];
vector<ll> g[MAX];
ll val[MAX];
ll par[MAX];

void dfs(ll hd, ll pr){
	dp[hd] = val[hd];
	par[hd] = pr;
	for(auto& hr : g[hd]){
		if(pr == hr){
			continue;
		}
		dfs(hr, hd);
		dp[hd] += dp[hr];
	}
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   	ll n = N;
	ll tot = 0;
	fori(n){
		tot+=pp[i];
		g[i].clear();
		val[i] = pp[i];
	}
	fori(n-1){
		ll ai = S[i], bi = D[i];
		g[ai].pb(bi);
		g[bi].pb(ai);
	}
	dfs(0, -1);
	ll mn = inf;
	ll lz = -1;
	fori(n){
		ll mx = tot - dp[i];
		for(auto& hr : g[i]){
			if(hr == par[i]){
				continue;
			}
			mx = max(mx, dp[hr]);
		}
		if(mx < mn){
			mn= mx;
			lz = i;
		}
	}
	return lz;
}

/*
int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();
}



*/

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