Submission #1256337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256337		avohado	Race (IOI11_race)	C++20	0 / 100	2 ms	4928 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
vector<pair<int, int>> g[maxn];
int p[1000000+1], mx=1e6, o[maxn], k;
bool ch[maxn];
void fu(int u, int r, int sm, int sh) {
	if(sm>k)return;
	p[sm]=min(p[sm], sh);
	for(auto i:g[u]) {
		if(i.f!=r&&!ch[i.f]) {
			fu(i.f, u, sm+i.s, sh+1);
		}
	}
}
void ex(int u, int r, int sm, int sh) {
	int sum=sm;
	if(sm>k)return;
	if(p[k-sm]<3e5) {
		mx=min(mx, sh+p[k-sm]);
	}
	for(auto i:g[u]) {
		if(i.f!=r&&!ch[i.f]) {
			ex(i.f, u, sum+i.s, sh+1);
		}
	}
}
int req(int n, int u, int v) {
	int sum=1;
	for(auto i:g[u]) {
		if(i.f!=v&&!ch[i.f]) {
			req(n, i.f, u);
			if(o[i.f]==-1) {
				o[u]=-1;
				return -1;
			}
			sum+=o[i.f];
		}
	}
	if(sum>=n/2) {
		ch[u]=1;
		vector<pair<int, int>> j;
		for(auto i:g[u]) {
			if(!ch[i.f]) {
				ex(i.f, u, i.s, 1);
				fu(i.f, u, i.s, 1);
				j.push_back({i.f, o[i.f]});
			}
		}
		for(auto i:j) {
			if(i.s>1) {
				for(int i=1; i<=k; i++) {
					p[i]=3e5;
				}
				req(i.s, i.f, i.f);
			}
		}
		o[u]=-1;
		return -1;
	}
	o[u]=sum;
	return sum;
}
int best_path(int n, int k1, int h[][2], int l[]) {
	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]});
	}
	k=k1;
	req(n, 0, 0);
	return (mx==1e6?-1:mx);
}

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