제출 #1273220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273220		arkanefury	경주 (Race) (IOI11_race)	C++20	0 / 100	3 ms	332 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define FOR(x, n, m, d) for(int x = n; x <= m; x += d)
#define all(v) v.begin(), v.end()
#define S second
#define F first
#define nikita ios_base::sync_with_stdio(0), cin.tie(0);
#define pb push_back
using namespace std;
const int N = 5e5+5;
int a[N], b[N], c[N], n, m, l, ans = 2e9, k, sz[N], siz, d[N];
map<int, int>mp;
bool used[N];
vector <pair<int, int>> g[N];
void dfs(int v, int p = 0){
	sz[v] = 1;
	for(auto i : g[v]){
		if(used[i.F] || p == i.F)continue;
		dfs(i.F, v);
		sz[v] += sz[i.F];
	}
}
int find_c(int v, int p = 0){
	for(auto i : g[v]){
		if(used[i.F] || i.F == p)continue;
		if(sz[i.F] * 2 > siz)return find_c(i.F, v);
	}
	return v;
}
void check(int v, int p, int cnt){
	if(cnt > m)return;
	if( mp[ m - cnt ] )ans = min(ans, mp[ m - cnt ] + d[v]);
	if(cnt == m)ans = min(ans, mp[cnt]);
	for(auto i : g[v]){
		if(i.F != p || used[i.F])continue;
		d[i.F] = d[v] + 1;
		check(i.F, v, cnt + i.S);
	}
}
void go(int v, int p, int cnt){
	if(cnt > m)return;
	if(!mp[cnt] && cnt)mp[cnt] = d[v];
	else mp[cnt] = min(mp[cnt], d[v]);
	for(auto i : g[v]){
		if(i.F == p || used[i.F])continue;
		d[i.F] = d[v] + 1;
		go(i.F, v, cnt + i.S);
	}
}
void centroid(int v){
	dfs(v);
	siz = sz[v];
	v = find_c(v);
	d[v] = 0;
	mp.clear();
	mp[0] = 0;
	used[v] = 1;
	for(auto i : g[v]){
	   	if(!used[i.F]){
	   	  d[i.F]= 1;
		  check(i.F, v, i.S);
	    }
		if(!used[i.F]){
	    	d[i.F] = 1;
	      	go(i.F, v, i.S);
	    }
	}
	for(auto i : g[v]){
		if(!used[i.F])centroid(i.F);
	}
}
int best_path(int N, int K, int H[][2], int L[])
{
	nikita
	n = N, m = K;
	FOR(i, 0, n-2, 1){
	g[H[i][0]].pb({H[i][1], L[i]});
	g[H[i][1]].pb({H[i][0], L[i]});
    }
	centroid(0);
	if(ans==2e9)return -1;
	return ans;
}

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