제출 #555542

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

race

#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int mxN = 1e6+5;
using pii = pair<int,int>;
vector<pii> tr[mxN];
int sbsz[mxN], seen[mxN], N, K, res = LLONG_MAX, within;
int gsb(int x, int p=-1) {
	sbsz[x] = 1ll;
	#define nn it.second
	for(auto it : tr[x]) if(!seen[nn] && nn != p) sbsz[x] += gsb(nn, x);
	return sbsz[x];
}
int gc(int x, int p=-1) {
	for(auto it : tr[x]) if(!seen[nn] && nn != p && sbsz[nn]*2ll>within) return gc(nn,x);
	seen[x]=1; return x;
}
gp_hash_table<int,int> rol, loc;
void pdfs(int x, int p, int dist, int len) {
	assert(!seen[x]);
	if(dist > K) return;
	if(loc.find(dist) == loc.end()) loc[dist] = len; else loc[dist] = min(loc[dist], len);
	for(auto it : tr[x]) if(!seen[nn] && nn != p) {
		pdfs(nn, x, dist + it.first, len+1ll);
	}
}
void de(int x){
	within = gsb(x,-1);
	int cen = gc(x,-1);
	rol.clear(); loc.clear();
	for(auto it : tr[cen]) if(!seen[nn]) {
		loc.clear();
		pdfs(nn, cen, it.first, 1ll);
		for(auto en : loc) {
			if(K-en.first < 0) continue; 
			if(rol.find(K-en.first) != rol.end()) res = min(res, en.second+rol[K-en.first]);
		}
		for(auto en : loc) { if(en.first < 0 || en.first > K) continue; if(rol.find(en.first) == rol.end()) rol[en.first] = en.second; else rol[en.first] = min(rol[en.first], en.second); }
	}

	for(auto it : tr[cen]) if(!seen[nn]) {
		de(nn);
	}
}
signed best_path(signed n, signed k, signed h[][2], signed l[]) {
	N = n, K = k;
	memset(sbsz, 0, sizeof sbsz);
	memset(seen, 0, sizeof seen);
	res = LLONG_MAX;
	within = -1;
	for(int i = 0; i < mxN; i++) tr[i].clear();
	rol.clear();
	loc.clear();

	
	for(int i = 0; i < N-1; i++) {
		int a = h[i][0], b = h[i][1], w = l[i];
		tr[a].push_back({w,b});
		tr[b].push_back({w,a});
	}
	de(0);
	if(res == LLONG_MAX) return -1; else return res;
}

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