Submission #953430

#	Time	Username	Problem	Language	Result	Execution time	Memory
953430		vjudge1	Race (IOI11_race)	C++17	0 / 100	3 ms	11868 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;
}
///////////////////////////////////////////////////////////

ll n,k,u,v,w;
vpl ad[200005],val;
vl tm(200005),vi(200005);

void dfs1(ll u,ll p=-1){
	ll t=1;
	each(v,ad[u])if(v.f!=p&&!vi[v.f]){
		dfs1(v.f,u);
		t+=tm[v.f];
	}
	tm[u]=t;
}

void dfs2(ll u,ll p=-1,ll d=0,ll pr=0){
	each(v,ad[u])if(v.f!=p&&!vi[v.f]){
		val.pb({d+v.s,pr+1});
		dfs2(v.f,u,d+v.s,pr+1);
	}
}

ll cent(ll u){
	dfs1(u);
	ll c=u,b=-1,a=u,r=-1;
	while(true){
		each(v,ad[c])if(!vi[v.f]&&v.f!=b&&tm[u]/2<tm[v.f]){
			c=v.f;
			break;
		}
		if(a==c)break;
		b=a,a=c;
	}
	val.clear();
	val.pb({0,0});
	dfs2(c);
	sor(val);
	for(ll i=0,j=sz(val)-1;i<j;i++){
		while(i+1<j&&k<=val[i].f+val[j-1].f)j--;
		if(k==val[i].f+val[j].f){
			if(r==-1)r=val[i].s+val[j].s;
			else ckmin(r,val[i].s+val[j].s);
		}
		while(i<j&&val[i].f==val[i+1].f)i++;
	}
	vi[c]=1;
	each(v,ad[c])if(!vi[v.f]){
		ll t=cent(v.f);
		if(r==-1)r=t;
		else if(t!=-1)ckmin(r,t);
	}
	return r;
}

//void solve(){
int best_path(int N,int K,int H[][2],int L[]){
	//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});
	}
	return cent(0);
}
/*
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