제출 #1144894

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144894		nurkhat_26	경주 (Race) (IOI11_race)	C++20	100 / 100	423 ms	52316 KiB

race

#include <bits/stdc++.h>
//#define int long long
#define FREOPEN  freopen(".in", "r", stdin);  freopen(".out", "w", stdout);
#define sonic ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FORR( i, x, n, d ) for( int i = x; i >= n; i -= d )
#define FOR( i, x, n, d ) for( int i = x; i <= n; i += d )
#define all(x) (x).begin(), (x).end()
#define pss pair<string,string>
#define nextp next_permutation
#define pii pair<int,int>
#define priq priority_queue
#define mii map<int,int>
#define sz(x) (x).size()
#define stirng string
#define str to_string
#define pb push_back
#define ll long long
#define rev reverse
#define endl '\n'
#define S second
#define F first
const int Pi=3.1415926535;
const ll inf=1e9+5;
const int MOD=1e9+7;
const int N1=1e6+123;
const int lol=63;
using namespace std;
int tc=1;
int n,a,b,c,k, siz;
int d[N1],ans=inf,pon[N1];
bool used[N1];
vector <pii> g[N1];
void dfs(int x, int p = -1){
	d[x] = 1;
	for(auto to : g[x]){
		if( to.F == p || used[to.F] )continue;
		dfs( to.F, x );
		d[x]+=d[to.F];
	}
}
int get(int x, int p){
	for(auto to : g[x]){
		if( to.F == p || used[to.F] ) continue;
		if( d[to.F] + d[to.F] > siz ) return get(to.F,x);
	} return x;
}
void add(int x, int p, int sum=0, int d=1){
	if(sum>k)return;
	ans=min(ans,pon[k-sum]+d);
	for(auto to : g[x]){
		if( used[to.F] || to.F==p ) continue;
		add( to.F, x, sum + to.S, d+1 );
	}
}void upd(int x, int p, int sum=0, int d=1){
	if(sum>k)return;
	pon[sum]=min(pon[sum], d);
	for(auto to : g[x]){
		if( used[to.F] || to.F==p ) continue;
		upd( to.F, x, sum+to.S, d+1 );
	}
}
void del(int x, int p, int sum=0, int d=1){
	if(sum>k)return;
	pon[sum]=inf;
	for(auto to : g[x]){
		if( used[to.F] || to.F==p ) continue;
		del( to.F, x, sum+to.S, d+1 );
	}
}
void calc(int x, int p = -1){
	dfs(x); siz = d[x];
	x=get(x, -1); used[x] = true;
	pon[0] = 0;
	for(auto to : g[x]){
		if(used[to.F] || to.F==p)continue;
		add(to.F,x,to.S); upd(to.F, x, to.S);
	}
	for(auto to : g[x]){
		if(used[to.F] || to.F==p)continue;
		del(to.F, x, to.S);
	}
	for(auto to : g[x]){
		if( used[to.F] || to.F == p )continue;
		calc(to.F,x);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	n = N, k = K;
	FOR(i,0,k,1)pon[i]=inf;
	FOR(i,0,n-2,1){
		int a=H[i][0],b=H[i][1];
		a++; b++;
		g[a].pb({b,L[i]});
		g[b].pb({a,L[i]});
	}calc(1);
	if(ans==inf)ans=-1;
	return ans;
}







 

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