Submission #953934

#	Time	Username	Problem	Language	Result	Execution time	Memory
953934		vjudge1	Race (IOI11_race)	C++17	100 / 100	887 ms	57408 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 INF=1e18;
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];
map<ll,ll>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){
	if(valt.find(d)!=valt.end())ckmin(valt[d],pr);
	else valt[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[0]=0;
	ll r=INF;
	each(v,ad[u])if(!cdv[v.f]){
		cdcd(v.f,u,1,v.s);
		ll pt=sz(val)-1;
		/*cout<<u<<":"<<nl;
		each(i,val)cout<<i.f<<" "<<i.s<<nl;
		cout<<":"<<nl;
		each(i,valt)cout<<i.f<<" "<<i.s<<nl;*/
		if(sz(val)<sz(valt))swap(valt,val);
		each(i,valt){
			if(k<i.f)break;
			if(val.find(k-i.f)!=val.end()){
				ckmin(r,val[k-i.f]+i.s);
			}
		}
		each(i,valt)
			if(val.find(i.f)!=val.end())ckmin(val[i.f],i.s);
			else val[i.f]=i.s;
		valt.clear();
	}
	//cout<<":"<<r<<nl;
	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(0);
	//if(w==INF)cout<<-1;
	//else cout<<w;
	if(w==INF)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;
}*/

Compilation message (stderr)

race.cpp: In function 'll cd(ll)':
race.cpp:89:6: warning: unused variable 'pt' [-Wunused-variable]
   89 |   ll pt=sz(val)-1;
      |      ^~

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