Submission #972065

#	Time	Username	Problem	Language	Result	Execution time	Memory
972065		ghostlywalrus	Race (IOI11_race)	C++17	100 / 100	338 ms	31824 KiB

race

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define ll long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())
#define all(a) (a).begin(), a.end()
#define dbg(v)                                                                 \
    cout << "Line(" << _LINE << ") -> " << #v << " = " << (v) << endl;

int const INF = 0x3f3f3f3f;
ll const LINF = 0x3f3f3f3f3f3f3f3fll;

const int maxn = 2e5+10;
vector<PI> adj[maxn];
int subsize[maxn];
bool isremoved[maxn];

int get_subsize(int x, int prev=-1){
	 subsize[x] = 1;

	 for (auto [nex, w] : adj[x]){
	 	if (nex == prev || isremoved[nex]) continue;
		subsize[x] += get_subsize(nex, x);
	 }

	 return subsize[x];
}

int get_centroid(int x, int tsize, int prev=-1){
	 for (auto [nex, w] : adj[x]){
	 	if (nex == prev || isremoved[nex]) continue;
		if (subsize[nex] * 2 > tsize) return get_centroid(nex, tsize, x);
	 }

	 return x;
}

const int maxk = 1e6+10;
int dp[maxk];

int k;
int maxdep;

void dfs1(int x, int cent, int d, int cnt=1, int prev=-1){
	if (d > k) return;

	for (auto [nex, w] : adj[x]){
	 	if (nex == prev || isremoved[nex]) continue;
		dfs1(nex, cent, d+w, cnt+1, x);
	}
 	
	maxdep = max(maxdep, d);
	dp[d] = min(dp[d], cnt);
}

int ans;
void dfs2(int x, int cent, int d, int cnt=1, int prev=-1){
	 if (d > k) return;

	 for (auto [nex, w] : adj[x]){
	 	if (nex == prev || isremoved[nex]) continue;
		dfs2(nex, cent, d+w, cnt+1, x);
	 }
	
	 if (k-d <= maxdep) ans = min(ans, cnt + dp[k-d]);
}


void build_decomp(int x){
	 int cent = get_centroid(x, get_subsize(x));
	 isremoved[cent] = true;

	 for (int i = 0; i <= maxdep; ++i) dp[i] = INF;

	 maxdep = 0;

	 dp[0] = 0;
	 for (auto [nex, w] : adj[cent]){
	 	if (!isremoved[nex]){
			dfs2(nex, cent, w);
	 		dfs1(nex, cent, w);
		}
	 }

	for (auto [nex, w] : adj[cent]){
	 	if (isremoved[nex]) continue;
		build_decomp(nex);
	}
}



int best_path(int n, int K, int h[][2], int l[]){
	k = K;
	maxdep = k;
	ans = INF;

	for (int i = 0; i < n-1; ++i){
	 	adj[h[i][0]].pb({h[i][1], l[i]});
		adj[h[i][1]].pb({h[i][0], l[i]});
	}
	
	build_decomp(0);

	if (ans < INF) return ans;
	return -1;
}

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