Submission #953901

#	Time	Username	Problem	Language	Result	Execution time	Memory
953901		vjudge1	Race (IOI11_race)	C++17	0 / 100	4 ms	13656 KiB

race

#include "race.h"
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;

template<class T>using pq=priority_queue<T>;
template<class T>using V=vector<T>;
using ll=long long;
using str=string;
using pl=pair<ll,ll>;
using vl=V<ll>;
using vpl=V<pl>;
	
#define sz(x) ll((x).size())
#define bg(x) begin(x)
#define all(x) bg(x),end(x)
#define sor(x) sort(all(x))
#define ins insert
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ft front()
#define nl "\n"
	
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(ll i=(b)-1;i>=(a);--i)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)
#define each(a,x) for(auto &a:x)
	
template<class T>bool ckmin(T &a,const T &b){return b<a?a=b,1:0;}
template<class T>bool ckmax(T &a,const T &b){return a<b?a=b,1:0;}

const int dx[4]{1,0,-1,0},dy[4]{0,1,0,-1};
const ll MOD=1e9+7;
//const int MOD=998244353;

ll bp(ll a,ll b=MOD-2) {
	ll r=1;a%=MOD;
	while(b){
		if(b&1)r=(r*a)%MOD;
		a=(a*a)%MOD,b>>=1;
	}
	return r;
}
///////////////////////////////////////////////////////////

const int N = 200005;
ll n,k;
vl cdv(N),cdp(N),cdd(N);
vpl ad[N],val,valt;

void cdcp(ll u,ll p=-1){
	cdp[u]=1;
	each(v,ad[u])if(!cdv[v.f]&&v.f!=p)
		cdcp(v.f,u),cdp[u]+=cdp[v.f];
}
ll cdcf(ll u,ll t,ll p=-1){
	each(v,ad[u])if(!cdv[v.f]&&v.f!=p)
		if(t/2<cdp[v.f]){
			u=cdcf(v.f,t,u);
			break;
		}
	return u;
}
void cdcd(ll u,ll p,ll pr,ll d){
	valt.pb({d,pr});
	each(v,ad[u])if(!cdv[v.f]&&v.f!=p)
		cdcd(v.f,u,pr+1,d+v.s);
}
ll cd(ll u){
	cdcp(u);
	u=cdcf(u,cdp[u]);
	val.pb({0,0});
	ll r=MOD;
	each(v,ad[u])if(!cdv[v.f]){
		cdcd(v.f,u,1,v.s);
		sor(val),sor(valt);
		ll pt=sz(val)-1;
		each(i,valt){
			while(0<pt&&k<i.f+val[pt].f)pt--;
			if(k==i.f+val[pt].f)ckmin(r,i.s+val[pt].s);
		}
		while(!valt.empty())val.pb(valt.back()),valt.pop_back();
	}
	val.clear();
	cdv[u]=1;
	each(v,ad[u])if(!cdv[v.f])
		ckmin(r,cd(v.f));
	return r;
}

//void solve(){
int best_path(int N,int K,int H[][2],int L[]){
	ll u,v,w;
	//cin>>n>>k;
	n=N,k=K;
	F0R(i,n-1){
		//cin>>u>>v>>w;
		u=H[i][0],v=H[i][1],w=L[i];
		ad[u].pb({v,w});
		ad[v].pb({u,w});
	}
	w=cd(1);
	//if(w==MOD)cout<<-1;
	//else cout<<w;
	if(w==MOD)return -1;
	else return w;
}
/*int main(){
	cin.tie(0)->sync_with_stdio(0);
	#ifndef ONLINE_JUDGE
	freopen("test.in","r",stdin),freopen("test.out","w",stdout);
	#endif
	//int TC;cin>>TC;rep(TC)
	solve();
	return 1<<32;
}*/

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