Submission #831866

#	Time	Username	Problem	Language	Result	Execution time	Memory
831866		iskhakkutbilim	Race (IOI11_race)	C++17	9 / 100	41 ms	12304 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){
	st.insert(make_pair(depth[v], v));
	if(depth[v] >= k){
		auto it = st.lower_bound(make_pair(depth[v] - k, -100));
		while(it != st.end()){
			if(it->ff != depth[v] - k) break;
//			cout << "ans ";
//			cout << v << " " << it->ss << '\n';
			mn = min(mn, abs(edges[v] - edges[it->ss]));
			it++;
		}
	}
//	cout << v << " = ";
//	cout << depth[v] << "\n";
	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[]){
	
	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(0, 0);
	
	if(mn == n+1) mn = -1;
	return mn;
}

//main(){
//	int N, K; cin >> N >> K;
//	int H[N-1][2], L[N-1];
//	for(int i = 0; i < N-1; i++){
//		cin >> H[i][0] >> H[i][1];
//	}
//	for(int i = 0;i < N-1; i++) cin >> L[i];
//	cout << best_path(N, K, H, L);
//}

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