Submission #1266781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266781		cmiuc	Race (IOI11_race)	C++20	0 / 100	14 ms	28992 KiB

race

#include <iostream>
#include <queue>
#include <algorithm>
#include "race.h"

using namespace std;
int Ans = 1e9, Min[1<<20], block[1<<20], ch[1<<20], KK;
vector<pair<int,int>> nei[1<<20];

int centroid(int u, int p, int r){
	for (auto [i, w] : nei[u]){
		if (!block[i] and i != p and ch[i] * 2 > ch[r])
			return centroid(i, u, r);
	}
	return u;
}

void dfs0(int u, int p){
	ch[u] = 1;
	for (auto [i, w] : nei[u]){
		if (!block[i] and i != p)
			dfs0(i, u), ch[u] += ch[i];
	}
}

void dfs1(int u, int p, int L, int pathLen = 1){
	if (L <= KK)
		Ans = min(Ans, pathLen + Min[KK - L]);
	for (auto [i, w] : nei[u]){
		if (!block[i] and i != p)
			dfs1(i, u, L + w, pathLen + 1);
	}
}

void dfs2(int u, int p, int L, int pathLen = 1){
	if (L <= KK)
		Min[L] = min(Min[L], pathLen);
	for (auto [i, w] : nei[u]){
		if (!block[i] and i != p)
			dfs1(i, u, L + w, pathLen + 1);
	}
}

void dfs3(int u, int p, int L, int pathLen = 1){
	if (L <= KK)
		Min[L] = 1e9;
	for (auto [i, w] : nei[u]){
		if (!block[i] and i != p)
			dfs1(i, u, L + w, pathLen + 1);
	}
}

void dfs(int u){
	dfs0(u, u);
	int c = centroid(u, u, u);

	for (auto [i, l] : nei[c]){
		if (!block[i]){
			dfs1(i, c, l);
			dfs2(i, c, l);
		}
	}

	for (auto [i, l] : nei[c]){
		if (!block[i])
			dfs3(i, c, l);
	}
	block[c] = 1;

	for (auto [i, l] : nei[c]){
		if (!block[i])
			dfs(i);
	}
}

int best_path(int n, int k, int h[][2], int l[]){
	for (int i=0;i<n-1;i++){
		nei[h[i][0]].push_back({h[i][1], l[i]});
		nei[h[i][1]].push_back({h[i][0], l[i]});
	}
	KK = k;
	// cout<<KK<<endl;
	for (int i=1;i<(1<<20);i++)
		Min[i] = 1e9;
	dfs(0);

	

	if (Ans == 1e9)
		Ans = -1;
	return Ans;
}

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