Submission #749267

#	Time	Username	Problem	Language	Result	Execution time	Memory
749267		aedmhsn	Race (IOI11_race)	C++17	100 / 100	613 ms	27796 KiB

race

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>



using namespace std;
using namespace __gnu_pbds;

#define A first
#define B second
#define MP make_pair
#define ms(a, x) memset(a, x, sizeof(a)) 

#pragma GCC optimize ("Ofast") 
//#pragma GCC optimize ("trapv")

#define boost() ios_base::sync_with_stdio(false); cin.tie(0)

typedef __int128_t vl;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<long double, long double> pld;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const double PI = acos(-1);

const int mxN=2e5+5, LOG=21;


vector <vector<pii>> adj(mxN);

int sz[mxN], cnt[int(1e6)+5], ans=INF;
bool mark[mxN];

void dfs_sz(int u, int p){
	sz[u]=1;
	for(auto [v, x]:adj[u]){
		if(v == p || mark[v]) continue;
		dfs_sz(v, u);
		sz[u] += sz[v];
	}
	return;
}
int dfs_cntrd(int u, int p, int subsz){
	for(auto [v, x]:adj[u]){
		if(v == p || mark[v]) continue;
		if(sz[v] > subsz/2) return dfs_cntrd(v, u, subsz);
	}
	return u;
}
void dfs_cnt(int u, int x, int d, int p, int mode, int k){
	if(x > k) return;
	(mode ? (mode == 1 ? ans = min(ans, d+cnt[k-x]):cnt[x]=INF):cnt[x] = min(cnt[x], d));
	for(auto [v, dist]:adj[u]){
		if(mark[v] || v == p) continue;
		dfs_cnt(v, dist+x, d+1, u, mode, k);
	}
}
void decompose(int u, int subsz, int k){
	dfs_sz(u, -1);
	int cntrd = dfs_cntrd(u, -1, subsz);
	mark[cntrd]=1;
	for(auto [v, x]:adj[cntrd]){
		if(mark[v]) continue;
		dfs_cnt(v, x, 1, -1, 1, k);
		dfs_cnt(v, x, 1, -1, 0, k);
	}
	ans = min(ans, cnt[k]);
	for(auto [v, x]:adj[cntrd]){
		if(mark[v]) continue;
		dfs_cnt(v, x, 1, -1, 2, k);
	}
	for(auto [v, x]:adj[cntrd]){
		if(mark[v]) continue;
		decompose(v, sz[v], k);
	}
	return;
}

int best_path(int n, int k, int h[mxN][2], int l[mxN]){
	ms(cnt, INF);
	for(int i=0; i<n-1; i++){
		adj[h[i][0]+1].push_back({h[i][1]+1, l[i]});
		adj[h[i][1]+1].push_back({h[i][0]+1, l[i]});
	}
	decompose(1, n, k);
	if(ans == INF) return -1;
	else return ans;
}

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