Submission #1140931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140931		why1	Race (IOI11_race)	C++20	100 / 100	313 ms	110872 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define pii pair<ll,ll>
#define fi first
#define se second
#define sz size()
#define pb push_back

const int M = 2e5;
const ll INF = 1e9;

ll n,k;
//int H[M+1][2],L[M+1];

vector<pii> g[M+1];
ll dw[M+1],d[M+1];
set<pii> st[M+1];
ll ans=INF;

void calc(int v,int pr){
	for(auto [to,w]: g[v]){
		if(to!=pr){
			dw[to]=dw[v]+w;
			d[to]=d[v]+1;
			calc(to,v);
		}
	}
}

void dfs(int v,int pr){	
	st[v].insert({dw[v],d[v]});
	for(auto [to,w]: g[v]){
		if(to!=pr){
			dfs(to,v);	
			if(st[v].sz<st[to].sz)
				st[v].swap(st[to]);
			for(auto [Dw,D]: st[to]){
				ll x=k+2*dw[v]-Dw;	
				auto it=st[v].lower_bound({x,0});
				if(it!=st[v].end() && it->fi==x){
					ans=min(ans,D+it->se-2*d[v]);
				}
			}
			for(auto j: st[to]){
				st[v].insert(j);
			}
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]){
//int solve(){

//	cin>>n>>k;
	n=N,k=K;
	for(int i = 0; i < n-1; i++){
//	for(int i = 1; i <= n-1; i++){
		//cin>>H[i][0]>>H[i][1]>>L[i];
		H[i][0]++,H[i][1]++;
		g[H[i][0]].pb({H[i][1],L[i]});
		g[H[i][1]].pb({H[i][0],L[i]});
	}
	calc(1,-1);
	dfs(1,-1);
	if(ans==INF)
		ans=-1;
	return ans;
}
/*
int main(){
	cout<<solve();
	return 0;
}
*/

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