제출 #369588

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

race

#include "race.h"
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define ed <<endl;
vector<vector<pair<int, int>>> adj(2e5+5);
vector<int> sz(2e5+5);
int N;
int K;
int cur = -1;
vector<int> forb(2e5+5);
int findCentroid(int n, int node, int par){
	// cerr << imie(node) imie(par) ed;
	if(n == 1){
		cur = node;
		return 0;
	}
 	sz[node] = 1;
 	bool ok = 1;
 	for(int i=0;i<(int)adj[node].size();i++){
 		if(cur != -1){
 			return 0;
 		}
 		int v=adj[node][i].first;
 		if(v != par && !forb[v]){
 			sz[node] += findCentroid(n, v, node);
 			if(sz[v] > n / 2) ok = 0;
 		}
 	}
 	if(n - sz[node] > n / 2){
 		ok = 0;
 	}
 	if(ok){
 		cur = node;
 	}
 	return sz[node];
}

int ans = 2e5+5;
//map<cost, edgecount>
void dfs(int node, int par, int dist, int cost, map<int, int> &global){
	int k=K;
	if(cost > K){
		return;
	}
	if(cost == k){
		ans = min(ans, dist);
		return;
	}
	if(global[k-cost] != 0){
		ans = min(ans, global[k-cost]+dist);
	}
	for(int i=0;i<(int)adj[node].size();i++){
		int v = adj[node][i].first;
		if(!forb[v] && v != par){
			dfs(v,par,dist+1,cost+adj[node][i].second, global);
		}
	}
	if(global[cost] == 0){
		global[cost] = dist;
	}
	global[cost] = min(global[cost], dist);
}
void mysol(int node){
	
	int cnt = 0;
	function<void(int, int)> mdfs = [&](int curnode, int par){
		cnt++;
		for(int i=0;i<(int)adj[curnode].size();i++){
			int v = adj[curnode][i].first;
			if(!forb[v] && v != par){
				mdfs(v, curnode);
			}
		}
	};
	mdfs(node, -1);
	map<int, int> global;
	cur = -1;
	findCentroid(cnt, node, -1);
	forb[cur] = 1;
	dfs(cur, -1, 0, 0, global);
	// cerr << imie(cur) imie(cnt) ed;
	int me = cur;
	for(int i=0;i<(int)adj[me].size();i++){
		int v = adj[me][i].first;
		if(!forb[v]){
			mysol(v);
		}
	}
}
int best_path(int n, int k, int h[][2], int l[]){
	N=n;
	K=k;
 	for(int i =0;i<n-1;i++){
 		int u = h[i][0];
 		int v = h[i][1];
 		adj[u].push_back({v, l[i]});
 		adj[v].push_back({u, l[i]});
 	}
 	mysol(0);
 	return (ans > n ? -1 : ans);
}

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