Submission #1325940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325940		tte0	Race (IOI11_race)	C++17	100 / 100	274 ms	71380 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
struct mset{
	set<pair<int64_t,int32_t>> st;
	int xbias=0,ybias=0;
	inline int size(){
		return st.size();
	}
	inline int search(int x){
		auto it=st.lower_bound({x-xbias,-2147483647});
		if(it!=st.end() && (*it).first==x-xbias){
			return (*it).second+ybias;
		}
		return -2147483648;
	}
	inline void insert(int x,int y){
		st.insert({x-xbias,y-ybias});
	}
};
inline void swap(mset& a,mset& b){
	swap(a.st,b.st);
	swap(a.xbias,b.xbias);
	swap(a.ybias,b.ybias);
}

int n,k,ans=2147483647;
vector<vector<pair<int,int>>> adj;
vector<mset> st;

inline void dfs(int node,int p){
	// cerr<<"dfs: "<<node<<" "<<p<<endl;
	for(auto [i,w]:adj[node]){
		if(i==p)continue;
		dfs(i,node);
		// cerr<<"merging "<<i<<" >to> "<<node<<endl;
		st[i].xbias+=w;
		st[i].ybias++;
		if(st[i].size()>st[node].size()){
			swap(st[i],st[node]);
		}
	
		auto it=st[i].st.begin();
		for(;it!=st[i].st.end();it++){
			int t=st[node].search(k - ((*it).first+st[i].xbias));
			if(t!=-2147483648){
				// cerr<<"ans"<<endl;
				ans=min(ans,t+((*it).second)+st[i].ybias);
			}
		}

		it=st[i].st.begin();
		for(;it!=st[i].st.end();it=st[i].st.erase(it)){
			st[node].insert((*it).first+st[i].xbias,(*it).second+st[i].ybias);
		}
	}
	st[node].insert(0,0);

	// cerr<<"st["<<node<<"]: ";for(auto [a,b]:st[node].st)cerr<<"("<<a+st[node].xbias<<","<<b+st[node].ybias<<") ";cerr<<endl;

	int t=st[node].search(k);
	if(t!=-2147483648){
		// cerr<<"ass"<<endl;
		ans=min(ans,t);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N;
	k=K;
	st.resize(n);
	adj.resize(n);
	for(int i=0;i<n-1;i++){
		adj[H[i][0]].push_back({H[i][1],L[i]});
		adj[H[i][1]].push_back({H[i][0],L[i]});
	}

	dfs(0,-1);
	return ans==2147483647?-1:ans;
}

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