제출 #172440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
172440		lobo_prix	경주 (Race) (IOI11_race)	C++17	0 / 100	6 ms	5112 KiB

race

#include <bits/stdc++.h>

using namespace std;using f64 = double;using i64=long long;using u64=unsigned long long;
template<typename T> using Arr=vector<T>;
#define hfor(v, s, e) for(int v=(s);(s)<=v&&v<(e);++v)//half-opened range
#define hfori(v, s, e) for(int v=(e)-1;(s)<=v&&v<(e);--v)//inversion
#define hforo(v, s, e) int v=(s);for(;(s)<=v&&v<(e);++v)//out declaration
#define hforoi(v, s, e) int v=(e)-1; for(;(s)<=v&&v<(e);--v)
#define cfor(v, s, e) hfor(v,(s),(e)+1)//closed range
#define cfori(v, s, e) hfori(v,(s),(e)+1)
#define cforo(v, s, e) hforo(v,(s),(e)+1)
#define cforoi(v, s, e) hforoi(v,(s),(e)+1)
#define rep(v,x) hfor(v,0,(x))
#define repi(v,x) hfori(v,0,(x))
#define repo(v,x) hforo(v,0,(x))
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pushb push_back
#define pushf push_front
#define popb pop_back
#define popf pop_front
#define empl emplace
#define emplb emplace_back
#define emplf emplace_front
#define fi first
#define se second
#define cxp constexpr
#define PQ std::priority_queue

#ifndef DEBUG
	#pragma GCC optimize ("Ofast")
	auto __PRE_RUN__=(ios::sync_with_stdio(0), cin.tie(0), cout.tie(0),(cout<<fixed<<setprecision(11)), 0);
#endif

template<typename T> cxp T inf() { return numeric_limits<T>::max() / 2; }
auto mapf(auto a, auto f){for(auto& x:a)x=f(x); return a;}
int rd(int lb, int ub){static mt19937 rng(time(0)^i64(new int)); return uniform_int_distribution<int>(lb, ub-1)(rng);}
int rd(int ub=inf<int>()){return rd(0,ub);}
const f64 pi=acosl(-1);
#define endl '\n'//not interactive?
#define int i64//MLE?
using pint = pair<int,int>;
using tint = tuple<int,int,int>;

const int N=200000;
int n,k;
Arr<pint> t[N];
int s[N];
int d[N];

int ct(int v, int sz_tot){
	int mx=-1;
	for(auto i:t[v])
		if(!d[i.fi] and (mx<0 or s[mx]<s[i.fi]))
			mx=i.fi;

	if(mx<0 or s[mx]*2<=sz_tot)
		return v;
	d[v]++;
	int ret=ct(mx, sz_tot);
	d[v]--;
	return ret;
}

int recalc(int v){
	d[v]++;
	s[v]=1;
	for(auto i:t[v])
		if(!d[i.fi])
			s[v]+=recalc(i.fi);
	d[v]--;
	return s[v];
}

void get_paths(int v, int dist, int cnt, multiset<pint>& z){
	z.insert({dist,cnt});
	if(d[v])
		return;
	d[v]++;
	for(auto i:t[v])
		//if(!d[i.fi])
			get_paths(i.fi, dist+i.se, cnt+1, z);
	d[v]--;
}

int f(int v){
	recalc(v);
	v=ct(v, s[v]);

	d[v]++;
	int ret=inf<int>();

	multiset<pint> z;
	for(auto i:t[v]){
		multiset<pint> y;
		//if(!d[i.fi])
			get_paths(i.fi, i.se, 1, y);

		for(auto j:y){
			auto it = z.lower_bound({k-j.fi,0});
			if(it!=z.end() and it->fi==k-j.fi)
				ret=min(ret, j.se+it->se);
		}
		z.insert(all(y));
	}

	for(auto i:t[v])
		if(!d[i.fi])
			ret=min(ret, f(i.fi));
	//d[v]--;
	return ret;
}

signed best_path(signed n, signed k, signed h[][2], signed l[]){
	rep(i,n-1){
		t[h[i][0]].pushb({h[i][1],l[i]});
		t[h[i][1]].pushb({h[i][0],l[i]});
	}
	recalc(0);
	int ans=f(0);
	return ans==inf<int>()?-1:ans;
}

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