답안 #166021

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
166021	2019-11-30T08:58:13 Z	JustInCase	경주 (Race) (IOI11_race)	C++17	100 / 100	651 ms	33016 KB

race

#include <iostream>
#include <vector>
#include <cstring>

const int32_t MAX_N = 2e5;
const int32_t MAX_K = 1e6;

#ifdef LOCAL
	#include "grader.cpp"
#endif
#ifndef LOCAL
	#include "race.h"
#endif

struct Vertex {
	bool solved;
	int32_t subtree;
	std::vector< std::pair< int32_t, int32_t > > v;
};

int32_t k, ans = -1, dists[MAX_K + 5];
Vertex g[MAX_N + 5];

void dfs_subtree(int32_t u, int32_t par) {
	g[u].subtree = 1;
	for(auto &e : g[u].v) {
		auto v = e.first;
		if(!g[v].solved && v != par) {
			dfs_subtree(v, u);
			g[u].subtree += g[v].subtree;
		}
	}
}

int32_t dfs_centroid(int32_t u, int32_t par, int32_t subtree) {
	for(auto &e : g[u].v) {
		auto v = e.first;
		if(!g[v].solved && v != par && g[v].subtree > subtree / 2) {
			return dfs_centroid(v, u, subtree);
		}
	}

	return u;
}

void dfs_ans(int32_t u, int32_t par, int32_t d, int32_t cntEdges) {
	if(d > k) {
		return;
	}

	if(dists[k - d] != -1) {
		if(ans == -1 || ans > cntEdges + dists[k - d]) {
			ans = cntEdges + dists[k - d];
		}
	}

	for(auto &e : g[u].v) {
		auto v = e.first;
		auto w = e.second;

		if(!g[v].solved && v != par) {
			dfs_ans(v, u, d + w, cntEdges + 1);
		}
	}
}

void dfs_add(int32_t u, int32_t par, int32_t d, int32_t cntEdges) {
	if(d > k) {
		return;
	}

	if(dists[d] == -1 || dists[d] > cntEdges) {
		dists[d] = cntEdges;
	}

	for(auto &e : g[u].v) {
		auto v = e.first;
		auto w = e.second;

		if(!g[v].solved && v != par) {
			dfs_add(v, u, d + w, cntEdges + 1);
		}
	}
}

void dfs_clear(int32_t u, int32_t par, int32_t d) {
	if(d > k) {
		return;
	}
	dists[d] = -1;

	for(auto &e : g[u].v) {
		auto v = e.first;
		auto w = e.second;

		if(!g[v].solved && v != par) {
			dfs_clear(v, u, d + w);
		}
	}
}

void solve(int32_t u) {
	dfs_subtree(u, -1);
	int32_t centroid = dfs_centroid(u, -1, g[u].subtree);
	
	dists[0] = 0;
	for(auto &e : g[centroid].v) {
		auto v = e.first;

		if(!g[v].solved) {
			dfs_ans(v, centroid, e.second, 1);
			dfs_add(v, centroid, e.second, 1);
		}
	}

	dfs_clear(centroid, -1, 0);
	g[centroid].solved = true;
	
	for(auto &e : g[centroid].v) {
		auto v = e.first;
		
		if(!g[v].solved) {
			solve(v);
		}
	}
}

int32_t best_path(int32_t n, int32_t _k, int32_t h[][2], int32_t l[]) {
	k = _k;
	for(int32_t i = 0; i < n - 1; i++) {
		g[h[i][0]].v.push_back({ h[i][1], l[i] });
		g[h[i][1]].v.push_back({ h[i][0], l[i] });
	}
	
	memset(dists, -1, sizeof(dists));
	solve(1);

	return ans;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	10488 KB	Output is correct
2	Correct	11 ms	10488 KB	Output is correct
3	Correct	11 ms	10488 KB	Output is correct
4	Correct	10 ms	10488 KB	Output is correct
5	Correct	10 ms	10488 KB	Output is correct
6	Correct	11 ms	10488 KB	Output is correct
7	Correct	11 ms	10488 KB	Output is correct
8	Correct	11 ms	10488 KB	Output is correct
9	Correct	11 ms	10488 KB	Output is correct
10	Correct	11 ms	10460 KB	Output is correct
11	Correct	11 ms	10492 KB	Output is correct
12	Correct	12 ms	10488 KB	Output is correct
13	Correct	23 ms	10616 KB	Output is correct
14	Correct	11 ms	10488 KB	Output is correct
15	Correct	11 ms	10488 KB	Output is correct
16	Correct	11 ms	10488 KB	Output is correct
17	Correct	11 ms	10488 KB	Output is correct
18	Correct	12 ms	10488 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	10488 KB	Output is correct
2	Correct	11 ms	10488 KB	Output is correct
3	Correct	11 ms	10488 KB	Output is correct
4	Correct	10 ms	10488 KB	Output is correct
5	Correct	10 ms	10488 KB	Output is correct
6	Correct	11 ms	10488 KB	Output is correct
7	Correct	11 ms	10488 KB	Output is correct
8	Correct	11 ms	10488 KB	Output is correct
9	Correct	11 ms	10488 KB	Output is correct
10	Correct	11 ms	10460 KB	Output is correct
11	Correct	11 ms	10492 KB	Output is correct
12	Correct	12 ms	10488 KB	Output is correct
13	Correct	23 ms	10616 KB	Output is correct
14	Correct	11 ms	10488 KB	Output is correct
15	Correct	11 ms	10488 KB	Output is correct
16	Correct	11 ms	10488 KB	Output is correct
17	Correct	11 ms	10488 KB	Output is correct
18	Correct	12 ms	10488 KB	Output is correct
19	Correct	11 ms	10488 KB	Output is correct
20	Correct	11 ms	10488 KB	Output is correct
21	Correct	12 ms	10576 KB	Output is correct
22	Correct	11 ms	10616 KB	Output is correct
23	Correct	12 ms	10616 KB	Output is correct
24	Correct	12 ms	10616 KB	Output is correct
25	Correct	12 ms	10616 KB	Output is correct
26	Correct	12 ms	10744 KB	Output is correct
27	Correct	12 ms	10616 KB	Output is correct
28	Correct	12 ms	10488 KB	Output is correct
29	Correct	11 ms	10616 KB	Output is correct
30	Correct	12 ms	10616 KB	Output is correct
31	Correct	12 ms	10616 KB	Output is correct
32	Correct	12 ms	10616 KB	Output is correct
33	Correct	23 ms	10616 KB	Output is correct
34	Correct	12 ms	10616 KB	Output is correct
35	Correct	12 ms	10616 KB	Output is correct
36	Correct	12 ms	10488 KB	Output is correct
37	Correct	11 ms	10616 KB	Output is correct
38	Correct	11 ms	10616 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	10488 KB	Output is correct
2	Correct	11 ms	10488 KB	Output is correct
3	Correct	11 ms	10488 KB	Output is correct
4	Correct	10 ms	10488 KB	Output is correct
5	Correct	10 ms	10488 KB	Output is correct
6	Correct	11 ms	10488 KB	Output is correct
7	Correct	11 ms	10488 KB	Output is correct
8	Correct	11 ms	10488 KB	Output is correct
9	Correct	11 ms	10488 KB	Output is correct
10	Correct	11 ms	10460 KB	Output is correct
11	Correct	11 ms	10492 KB	Output is correct
12	Correct	12 ms	10488 KB	Output is correct
13	Correct	23 ms	10616 KB	Output is correct
14	Correct	11 ms	10488 KB	Output is correct
15	Correct	11 ms	10488 KB	Output is correct
16	Correct	11 ms	10488 KB	Output is correct
17	Correct	11 ms	10488 KB	Output is correct
18	Correct	12 ms	10488 KB	Output is correct
19	Correct	174 ms	15464 KB	Output is correct
20	Correct	172 ms	15424 KB	Output is correct
21	Correct	189 ms	15352 KB	Output is correct
22	Correct	173 ms	15352 KB	Output is correct
23	Correct	123 ms	15700 KB	Output is correct
24	Correct	101 ms	15480 KB	Output is correct
25	Correct	190 ms	20408 KB	Output is correct
26	Correct	131 ms	21240 KB	Output is correct
27	Correct	229 ms	20476 KB	Output is correct
28	Correct	368 ms	30844 KB	Output is correct
29	Correct	323 ms	26744 KB	Output is correct
30	Correct	217 ms	20472 KB	Output is correct
31	Correct	223 ms	20472 KB	Output is correct
32	Correct	255 ms	20344 KB	Output is correct
33	Correct	304 ms	19192 KB	Output is correct
34	Correct	274 ms	19192 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	10488 KB	Output is correct
2	Correct	11 ms	10488 KB	Output is correct
3	Correct	11 ms	10488 KB	Output is correct
4	Correct	10 ms	10488 KB	Output is correct
5	Correct	10 ms	10488 KB	Output is correct
6	Correct	11 ms	10488 KB	Output is correct
7	Correct	11 ms	10488 KB	Output is correct
8	Correct	11 ms	10488 KB	Output is correct
9	Correct	11 ms	10488 KB	Output is correct
10	Correct	11 ms	10460 KB	Output is correct
11	Correct	11 ms	10492 KB	Output is correct
12	Correct	12 ms	10488 KB	Output is correct
13	Correct	23 ms	10616 KB	Output is correct
14	Correct	11 ms	10488 KB	Output is correct
15	Correct	11 ms	10488 KB	Output is correct
16	Correct	11 ms	10488 KB	Output is correct
17	Correct	11 ms	10488 KB	Output is correct
18	Correct	12 ms	10488 KB	Output is correct
19	Correct	11 ms	10488 KB	Output is correct
20	Correct	11 ms	10488 KB	Output is correct
21	Correct	12 ms	10576 KB	Output is correct
22	Correct	11 ms	10616 KB	Output is correct
23	Correct	12 ms	10616 KB	Output is correct
24	Correct	12 ms	10616 KB	Output is correct
25	Correct	12 ms	10616 KB	Output is correct
26	Correct	12 ms	10744 KB	Output is correct
27	Correct	12 ms	10616 KB	Output is correct
28	Correct	12 ms	10488 KB	Output is correct
29	Correct	11 ms	10616 KB	Output is correct
30	Correct	12 ms	10616 KB	Output is correct
31	Correct	12 ms	10616 KB	Output is correct
32	Correct	12 ms	10616 KB	Output is correct
33	Correct	23 ms	10616 KB	Output is correct
34	Correct	12 ms	10616 KB	Output is correct
35	Correct	12 ms	10616 KB	Output is correct
36	Correct	12 ms	10488 KB	Output is correct
37	Correct	11 ms	10616 KB	Output is correct
38	Correct	11 ms	10616 KB	Output is correct
39	Correct	174 ms	15464 KB	Output is correct
40	Correct	172 ms	15424 KB	Output is correct
41	Correct	189 ms	15352 KB	Output is correct
42	Correct	173 ms	15352 KB	Output is correct
43	Correct	123 ms	15700 KB	Output is correct
44	Correct	101 ms	15480 KB	Output is correct
45	Correct	190 ms	20408 KB	Output is correct
46	Correct	131 ms	21240 KB	Output is correct
47	Correct	229 ms	20476 KB	Output is correct
48	Correct	368 ms	30844 KB	Output is correct
49	Correct	323 ms	26744 KB	Output is correct
50	Correct	217 ms	20472 KB	Output is correct
51	Correct	223 ms	20472 KB	Output is correct
52	Correct	255 ms	20344 KB	Output is correct
53	Correct	304 ms	19192 KB	Output is correct
54	Correct	274 ms	19192 KB	Output is correct
55	Correct	22 ms	11128 KB	Output is correct
56	Correct	23 ms	11244 KB	Output is correct
57	Correct	108 ms	16888 KB	Output is correct
58	Correct	53 ms	16744 KB	Output is correct
59	Correct	143 ms	22492 KB	Output is correct
60	Correct	592 ms	28544 KB	Output is correct
61	Correct	252 ms	23624 KB	Output is correct
62	Correct	274 ms	23416 KB	Output is correct
63	Correct	336 ms	23356 KB	Output is correct
64	Correct	651 ms	23700 KB	Output is correct
65	Correct	278 ms	24312 KB	Output is correct
66	Correct	506 ms	33016 KB	Output is correct
67	Correct	144 ms	24164 KB	Output is correct
68	Correct	328 ms	24284 KB	Output is correct
69	Correct	332 ms	24312 KB	Output is correct
70	Correct	284 ms	23688 KB	Output is correct

답안 #166021

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 22.0 / 22.0

Subtask #4 57.0 / 57.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
22.0 / 22.0

Subtask #4
57.0 / 57.0