Submission #474474

#	Time	Username	Problem	Language	Result	Execution time	Memory
474474		disastah	Race (IOI11_race)	C++17	100 / 100	526 ms	103892 KiB

race

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ar array
using namespace std;
typedef long double ld;
typedef long long ll;
const int inf=1e9+1e8;
const ll linf=4e18+18;
const int N=2e5;
int n, k, h[N], ans=inf; ll dep[N];
map<ll,int> dp[N];
vector<ar<int,2>> g[N];
int get(int v, ll x) {
	return (dp[v].find(x)!=dp[v].end()?dp[v][x]:inf);
}
void dfs(int v, int p=-1) {
	dp[v][dep[v]]=h[v];
	for (auto &[u,c] : g[v]) {
		if (u!=p) {
			h[u]=h[v]+1, dep[u]=dep[v]+c;
			dfs(u,v);
			if (dp[u].size()>dp[v].size()) swap(dp[v],dp[u]);
			for (auto &[x,dh] : dp[u]) {
				ans=min(ans,dh+get(v,k-x+2*dep[v])-2*h[v]);
			}
			for (auto &[x,dh] : dp[u]) {
				if (dp[v].find(x)==dp[v].end()) dp[v][x]=dh;
				else dp[v][x]=min(dp[v][x],dh);
			}
		}
	}
}
int best_path(int n0, int k0, int h[][2], int l[]) {
	n=n0, k=k0;
	for (int i=0; i<n-1; ++i) {
		g[h[i][0]].push_back({h[i][1],l[i]});
		g[h[i][1]].push_back({h[i][0],l[i]});
	}
	dfs(0);
	return (ans<n?ans:-1);
}

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