제출 #1015576

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015576		ByeWorld	Traffic (IOI10_traffic)	C++14	100 / 100	1415 ms	142112 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<pii, int> ipii;
const int MAXN = 1e6+20;
const int MAXA = 9e3+20;
const ll INF = 1e18+10;
const int LOG = 19;
const int MOD = 1e9+7;
const int SQRT = 450;
const vector<int> NOL = {};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, 1, -1};
void chmx(ll &a, ll b){
	a = max(a, b);
}

int n; ll MN = INF, idx = 0;
ll sub[MAXN], val[MAXN], tot;
vector <int> adj[MAXN];

void bd(int nw, int par){
	sub[nw] = val[nw];
	for(auto nx : adj[nw]){
		if(nx==par) continue;
		bd(nx, nw);
		sub[nw] += sub[nx];
	}
}
void dfs(int nw, int par){
	ll te = tot-sub[nw];
	for(auto nx : adj[nw]){
		if(nx==par) continue;
		dfs(nx, nw);
		chmx(te, sub[nx]);
	}
	if(te < MN){
		MN = te; idx = nw;
	}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
	n = N;
	for(int i=1; i<=n; i++){ val[i] = pp[i-1]; tot += val[i]; }
	for(int i=0; i<n; i++){
		adj[S[i]+1].pb(D[i]+1); adj[D[i]+1].pb(S[i]+1);
	}
	bd(1, 0);
	dfs(1, 0);
	assert(idx != 0);
	return idx-1;
}

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