제출 #1144887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1144887		nurkhat_26	경주 (Race) (IOI11_race)	C++20	0 / 100	11 ms	23872 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;
int d[N1],ans=inf;
bool used[N1];
map <pii,int> mp;
vector <int> g[N1];
void dfs(int x, int p = -1){
	d[x] = 1;
	for(auto to : g[x]){
		if( to == p || used[to] )continue;
		dfs( to, x );
		d[x]+=d[to];
	}
}
int get(int x){
	bool ok;
	int Sz=d[x], p = -1;
	while(true){
		ok = false;
		for(auto to : g[x]){
			if( to == p || used[to] )continue;
			if( d[to]*2>=Sz ){
				p=x; x=to; ok=true;
			break;
		}
		} if(!ok)break;
	} return x;
}int pon[N1];
void add(int x, int p, int sum=0, int d=1){
	sum+=mp[{x,p}]; if(sum>k)return;
	ans=min(ans,pon[k-sum]+d);
	for(auto to : g[x]){
		if( used[to] || to==p ) continue;
		add( to, x, sum, d+1 );
	}
}void upd(int x, int p, int sum=0, int d=1){
	sum+=mp[{x,p}]; if(sum>k)return;
	pon[sum]=min( pon[sum], d );
	for(auto to : g[x]){
		if( used[to] || to==p ) continue;
		upd( to, x, sum, d+1 );
	}
}
void del(int x, int p, int sum=0, int d=1){
	sum+=mp[{x,p}]; if(sum>k)return;
	pon[sum]=inf;
	for(auto to : g[x]){
		if( used[to] || to==p ) continue;
		del( to, x, sum, d+1 );
	}
}
void calc(int x, int p = -1){
	dfs(x);
	x=get(x); used[x] = true;
	for(auto to : g[x]){
		if(used[to] || to==p)continue;
		add(to,x); upd(to,x);
	}
	for(auto to : g[x]){
		if(used[to] || to==p)continue;
		del(to, x);
	}
	ans=min(ans,pon[k]);
	for(auto to : g[x]){
		if( used[to] || to == p )continue;
		calc(to,x);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n = N, k = K;
	FOR(i,0,n-2,1){
		int a=H[i][0],b=H[i][1];
		g[a].pb(b);
		g[b].pb(a);
		mp[{a,b}]=mp[{b,a}]=L[i];
	}calc(1);
	return (ans!=inf ? ans : -1);
}







 

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