제출 #62444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62444		Sherazin	경주 (Race) (IOI11_race)	C++14	100 / 100	1228 ms	77736 KiB

race

//#include "race.h"
#include <bits/stdc++.h>

#define pii pair<int, int>
#define x first
#define y second

using namespace std;

const int N = 2e5 + 5;
const int M = 1e6 + 5;

int n, k, book;
int ans = -1;
int sub[N], dp[M], tim[M];
vector<pii> g[N];
bitset<N> chk;
int cent, mxnode;

int calcsz(int u, int p) {
	sub[u] = 1;
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) sub[u] += calcsz(v.x, u);
	return sub[u];
}

void centroid(int u, int p, int all) {
	int mxsub = all - sub[u];
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) {
		centroid(v.x, u, all);
		mxsub = max(mxsub, sub[v.x]);
	}
	if(mxsub < mxnode) cent = u, mxnode = mxsub;
}

void dfs(int u, int p, int len, int cnt) {
	if(len > k) return;
	if(tim[k - len] == book && (ans == -1 || cnt + dp[k - len] < ans)) ans = cnt + dp[k - len];
	if(len == k && (ans == -1 || cnt < ans)) ans = cnt;
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) dfs(v.x, u, len + v.y, cnt + 1);
}

void prep(int u, int p, int len, int cnt) {
	if(len > k) return;
	if(tim[len] < book || cnt < dp[len]) tim[len] = book, dp[len] = cnt;
	for(pii v : g[u]) if(v.x != p && !chk[v.x]) dfs(v.x, u, len + v.y, cnt + 1);
}

void dfs2(int u, int p, int cost, int edge, bool fill) {
	if(cost > k) return;
	if(!fill) {
		if(tim[k - cost] == book && (edge + dp[k - cost] < ans || ans == -1)) ans = edge + dp[k - cost];
		if(cost == k && (edge < ans || ans == -1)) ans = edge;
	} else if(tim[cost] < book || edge < dp[cost]) tim[cost] = book, dp[cost] = edge;
 
	for(pii v : g[u]) if(!chk[v.x] && v.x != p) {
		dfs2(v.x, u, cost + v.y, edge + 1, fill);
	}
}

void proc(int u) {
	book++;
	if(calcsz(u, u) <= 1) return;
	mxnode = sub[u] + 1;
	centroid(u, u, sub[u]);
	u = cent;
	//printf("%d\n", u);
	for(pii v : g[u]) if(!chk[v.x]) {
		dfs2(v.x, u, v.y, 1, false);
		dfs2(v.x, u, v.y, 1, true);
	}
	chk[u] = 1;
	for(pii v : g[u]) if(!chk[v.x]) proc(v.x);
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N, k = K;
	for(int i = 0; i < n - 1; i++) {
		g[H[i][0]].emplace_back(H[i][1], L[i]);
		g[H[i][1]].emplace_back(H[i][0], L[i]);
	}

	proc(0);
	return ans;
}

/*int main() {
	int n, k, h[100][2], l[100];
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n - 1; i++) {
		scanf("%d %d %d", &h[i][0], &h[i][1], &l[i]);
	}
	printf("%d", best_path(n, k, h, l));

	return 0;
}*/

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