Submission #429471

#	Time	Username	Problem	Language	Result	Execution time	Memory
429471		hibye1217	Race (IOI11_race)	C++17	43 / 100	3053 ms	34016 KiB

race

#ifndef NOTSUBMIT
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#endif // NOTSUBMIT

typedef long long ll;
typedef pair<ll, ll> pl2;
typedef pair<int, int> pi2;
#define fr first
#define sc second

vector<pl2> adj[200020];
bool chk[200020];
int sz[200020];

int siz(int now, int par){
	//cout << "  SIZ " << now << ' ' << par << endl;
	sz[now] = 1;
	for (pl2 p : adj[now]){
		//cout << "  P " << p.fr << ' ' << p.sc << endl;
		int nxt = p.fr;
		if (nxt == par || chk[nxt]){ continue; }
		//cout << "  ?? " << nxt << ' ' << now << endl;
		sz[now] += siz(nxt, now);
	}
	//cout << "    SIZE " << now << ' ' << sz[now] << endl;
	return sz[now];
}

int cen(int now){
	siz(now, -1);
	int ptr = now, tar = sz[now] / 2;
	int par = -1;
	while (1){
		bool flg = 1;
		for (pl2 p : adj[ptr]){
			int nxt = p.fr;
			if (par == nxt || chk[nxt] || sz[nxt] <= tar){ continue; }
			flg = 0; par = ptr; ptr = nxt; break;
		}
		if (flg){ return ptr; }
	}
}

int k;
deque<pi2> v;
int dp[1000020];
queue<int> q;

void dpf(int now, int par, int dep, ll dis){
	if (dis > k){ return; }
	v.push_back({dep, dis});
	for (pl2 p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (par == nxt || chk[nxt]){ continue; }
		dpf(nxt, now, dep+1, dis+dst);
	}
}

int ans = 1e9;
void f(int now){
	int r = cen(now);
	//cout << "CEN " << now << ' ' << r << endl;
	for (pl2 p : adj[r]){
		int nxt = p.fr; ll dis = p.sc;
		dpf(nxt, r, 1, dis);
		for (pi2 pp : v){
			int dep = pp.fr, dst = pp.sc;
			q.push(dst);
			//cout << "ANS " << dep << ' ' << dst << ' ';
			if (dp[k-dst] != -1){ ans = min(ans, dp[k-dst] + dep); }
			//cout << ans << endl;
		}
		for (pi2 pp : v){
			int dep = pp.fr, dst = pp.sc;
			//cout << "DP " << dst << ' ' << dp[dst] << ' ' << dep << endl;
			if (dp[dst] == -1){ dp[dst] = dep; }
			else{ dp[dst] = min(dp[dst], dep); }
		}
		v.clear();
	}
	while (!q.empty()){ dp[q.front()] = -1; q.pop(); }
	chk[r] = 1;
	for (pl2 p : adj[r]){
		int nxt = p.fr;
		if (chk[nxt]){ continue; }
		f(nxt);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	for (int i = 0; i < N-1; i++){
		adj[ H[i][0] ].push_back({ H[i][1], L[i] });
		adj[ H[i][1] ].push_back({ H[i][0], L[i] });
	}
	k = K; memset(dp, -1, sizeof(dp)); dp[0] = 0;
	f(0);
	if (ans == 1e9){ return -1; }
	else{ return ans; }
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57