Submission #831855

#	Time	Username	Problem	Language	Result	Execution time	Memory
831855		iskhakkutbilim	Race (IOI11_race)	C++17	0 / 100	2 ms	4948 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;
#define ff first
#define ss second

int n, k, mn;
vector< pair<int, int> > g[200005];
set<pair<long long, int> > st;
long long depth[200005];
int edges[200005];
void dfs(int v, int par){
	auto it = st.lower_bound(make_pair(depth[v] - k, -1));
	while(it != st.end()){
		if(it->ff != depth[v] - k) break;
		mn = min(mn, abs(edges[v] - edges[it->ss]));
	}
	for(auto [to, w] : g[v]){
		if(to == par) continue;
		depth[to] = depth[v] + w;
		edges[to] = edges[v] + 1;
		dfs(to, v);
	}
	st.erase(make_pair(depth[v], v));
}


int best_path(int N, int K, int H[][2], int L[]){
	st.insert({0, 0});
	n = N, k = K, mn = N+1;
	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(1, 1);
	
	if(mn == n+1) mn = -1;
	return mn;
}

//main(){
//	
//}

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