Submission #420073

#	Time	Username	Problem	Language	Result	Execution time	Memory
420073		hibye1217	Race (IOI11_race)	C++17	21 / 100	3063 ms	17988 KiB

race

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

typedef long long ll;
typedef pair<ll, ll> pll;
#define fr first
#define sc second

vector<pll> adj[200020];
bool chk[200020];
int sz[200020];
int dp[1000020];
vector<pll> v;

void siz(int now, int par){
	//cout << "SIZ " << now << endl;
	sz[now] = 1;
	for (pll p : adj[now]){
		int nxt = p.fr;
		if (nxt == par || chk[nxt]){ continue; }
		siz(nxt, now);
		sz[now] += sz[nxt];
	}
}

int cen(int now, int par){
	//cout << "CEN " << now << endl;
	siz(now, par);
	int n = sz[now];
	while (1){
		bool flg = 1;
		for (pll p : adj[now]){
			int nxt = p.fr;
			//cout << "p " << nxt << endl;
			if (nxt == par || chk[nxt]){ continue; }
			if (2*sz[nxt] > n){ par = now; now = nxt; flg = 0; break; }
		}
		if (flg){ return now; }
	}
}

void g(int now, int par, int dep, ll dis){
	//cout << "G " << now << endl;
	v.push_back({dep, dis});
	for (pll p : adj[now]){
		int nxt = p.fr; ll dst = p.sc;
		if (nxt == par || chk[nxt]){ continue; }
		g(nxt, now, dep+1, dis+dst);
	}
}

int ans = 1e9;
void f(int now, int par, ll k){
	//cout << "F " << now << ' ' << par << endl;
	now = cen(now, par);
	//cout << "cen " << now << endl;
	memset(dp, -1, sizeof(dp));
	for (pll p : adj[now]){
		int nxt = p.fr; ll dis = p.sc;
		g(nxt, now, 1, dis);
		for (pll q : v){
			int dep = q.fr; ll val = q.sc;
			//cout << "DP " << dep << ' ' << val << endl;
			if (k-val >= 0 && dp[k-val] != -1){
				//cout << "ans " << dep << ' ' << val << ' ' << dp[k-val] << endl;
				ans = min(ans, dep + dp[k-val]);
			}
		}
		for (pll q : v){
			int dep = q.fr; ll val = q.sc;
			if (val <= k){
				if (dp[val] == -1){ dp[val] = dep; }
				else{ dp[val] = min(dp[val], dep); }
			}
		}
		v.clear();
	}
	chk[now] = 1;
	for (pll p : adj[now]){
		int nxt = p.fr;
		if (chk[nxt]){ continue; }
		f(nxt, now, k);
	}
}

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] });
	}
	f(0, -1, K);
	if (ans == 1e9){ return -1; }
	else{ return ans; }
}

Compilation message (stderr)

race.cpp:5:8: warning: extra tokens at end of #endif directive [-Wendif-labels]
    5 | #endif NOTSUBMIT
      |        ^~~~~~~~~

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