답안 #41188 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
41188	2018-02-13T16:52:30 Z	Just_Solve_The_Problem	경주 (Race) (IOI11_race)	C++11	100 / 100	916 ms	43224 KB

race

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

using namespace std;

#define ll long long
#define pii pair < ll, ll >
#define mk make_pair
#define fr first
#define sc second
#define pb push_back
#define ok puts("ok");

const int N = (int)2e5 + 7;
const int nn = (int)1e6 + 7;

ll can[nn], mnpath[nn];
int n, k, book;
vector < pii > gr[N];
int sz[N];
bool del[N];
ll ans = -1;

void dfs(int v, int pr) {
	sz[v] = 1;
	for (auto to : gr[v]) {
		if (to.fr == pr || del[to.fr]) continue;
		dfs(to.fr, v);
		sz[v] += sz[to.fr];
	}
}

int findcentroid(int v) {
	int now = v;
	int siz = sz[v];
	int pr = -1;
	bool fl = 1;
	while (1) {
		fl = 1;
		for (auto to : gr[now]) {
			if (to.fr == pr || del[to.fr]) continue;
			if (sz[to.fr] * 2 >= siz) {
				pr = now;
				now = to.fr;
				fl = 0;
				break;
			}
		}
		if (fl) break;
	}
	return now;
}

void dfs1(int v, int pr, int curcost, int curlen, int tp) {
	if (curcost > k)
		return ;
	if (tp == 0) {
		if (can[k - curcost] == book) {
			if (curlen + mnpath[k - curcost] < ans || ans == -1) {
				ans = curlen + mnpath[k - curcost];
			}
		}
		if (curcost == k && (curlen < ans || ans == -1)) {
			ans = curlen;
		}
	} else {
		if (can[curcost] < book) {
			can[curcost] = book;
			mnpath[curcost] = curlen;
		} else if (curlen < mnpath[curcost]) {
			can[curcost] = book;
			mnpath[curcost] = curlen;
		}
	}
	for (auto to : gr[v]) {
		if (to.fr == pr || del[to.fr]) continue;
		dfs1(to.fr, v, curcost + to.sc, curlen + 1, tp);
	}
}                 

void compute(int v) {
	dfs(v, 0);
	if (sz[v] <= 1)
		return ;
	int centroid = -1;
	centroid = findcentroid(v);
	book++;
	for (auto to : gr[centroid]) {
		if (del[to.fr]) continue;
		dfs1(to.fr, centroid, to.sc, 1, 0);
		dfs1(to.fr, centroid, to.sc, 1, 1);
	}
	// printf("### %d %d\n", centroid, ans);     
	del[centroid] = 1;
	for (auto to : gr[centroid]) {
		if (del[to.fr]) continue;
		compute(to.fr);
	}
}

int best_path (int _n, int _k, int _h[][2], int _l[]) {
	n = _n; k = _k;	
	for (int i = 0; i < n - 1; i++) {
		ll u, v, w;
		u = _h[i][0] + 1; v = _h[i][1] + 1; w = _l[i];
		gr[v].pb(mk(u, w));
		gr[u].pb(mk(v, w));
	}
	compute(1);       
	return ans;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	5220 KB	Output is correct
3	Correct	5 ms	5220 KB	Output is correct
4	Correct	5 ms	5220 KB	Output is correct
5	Correct	5 ms	5220 KB	Output is correct
6	Correct	6 ms	5296 KB	Output is correct
7	Correct	6 ms	5320 KB	Output is correct
8	Correct	5 ms	5336 KB	Output is correct
9	Correct	6 ms	5336 KB	Output is correct
10	Correct	6 ms	5336 KB	Output is correct
11	Correct	6 ms	5340 KB	Output is correct
12	Correct	5 ms	5340 KB	Output is correct
13	Correct	6 ms	5340 KB	Output is correct
14	Correct	5 ms	5340 KB	Output is correct
15	Correct	5 ms	5340 KB	Output is correct
16	Correct	5 ms	5372 KB	Output is correct
17	Correct	6 ms	5372 KB	Output is correct
18	Correct	6 ms	5372 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	5220 KB	Output is correct
3	Correct	5 ms	5220 KB	Output is correct
4	Correct	5 ms	5220 KB	Output is correct
5	Correct	5 ms	5220 KB	Output is correct
6	Correct	6 ms	5296 KB	Output is correct
7	Correct	6 ms	5320 KB	Output is correct
8	Correct	5 ms	5336 KB	Output is correct
9	Correct	6 ms	5336 KB	Output is correct
10	Correct	6 ms	5336 KB	Output is correct
11	Correct	6 ms	5340 KB	Output is correct
12	Correct	5 ms	5340 KB	Output is correct
13	Correct	6 ms	5340 KB	Output is correct
14	Correct	5 ms	5340 KB	Output is correct
15	Correct	5 ms	5340 KB	Output is correct
16	Correct	5 ms	5372 KB	Output is correct
17	Correct	6 ms	5372 KB	Output is correct
18	Correct	6 ms	5372 KB	Output is correct
19	Correct	5 ms	5372 KB	Output is correct
20	Correct	5 ms	5372 KB	Output is correct
21	Correct	7 ms	5372 KB	Output is correct
22	Correct	14 ms	12156 KB	Output is correct
23	Correct	15 ms	12156 KB	Output is correct
24	Correct	16 ms	13692 KB	Output is correct
25	Correct	13 ms	13692 KB	Output is correct
26	Correct	10 ms	13692 KB	Output is correct
27	Correct	7 ms	13692 KB	Output is correct
28	Correct	9 ms	13692 KB	Output is correct
29	Correct	11 ms	13692 KB	Output is correct
30	Correct	12 ms	13692 KB	Output is correct
31	Correct	12 ms	13692 KB	Output is correct
32	Correct	14 ms	13692 KB	Output is correct
33	Correct	15 ms	14844 KB	Output is correct
34	Correct	16 ms	14844 KB	Output is correct
35	Correct	16 ms	15356 KB	Output is correct
36	Correct	17 ms	15996 KB	Output is correct
37	Correct	13 ms	15996 KB	Output is correct
38	Correct	10 ms	15996 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	5220 KB	Output is correct
3	Correct	5 ms	5220 KB	Output is correct
4	Correct	5 ms	5220 KB	Output is correct
5	Correct	5 ms	5220 KB	Output is correct
6	Correct	6 ms	5296 KB	Output is correct
7	Correct	6 ms	5320 KB	Output is correct
8	Correct	5 ms	5336 KB	Output is correct
9	Correct	6 ms	5336 KB	Output is correct
10	Correct	6 ms	5336 KB	Output is correct
11	Correct	6 ms	5340 KB	Output is correct
12	Correct	5 ms	5340 KB	Output is correct
13	Correct	6 ms	5340 KB	Output is correct
14	Correct	5 ms	5340 KB	Output is correct
15	Correct	5 ms	5340 KB	Output is correct
16	Correct	5 ms	5372 KB	Output is correct
17	Correct	6 ms	5372 KB	Output is correct
18	Correct	6 ms	5372 KB	Output is correct
19	Correct	172 ms	15996 KB	Output is correct
20	Correct	164 ms	15996 KB	Output is correct
21	Correct	217 ms	15996 KB	Output is correct
22	Correct	220 ms	15996 KB	Output is correct
23	Correct	116 ms	15996 KB	Output is correct
24	Correct	77 ms	15996 KB	Output is correct
25	Correct	192 ms	15996 KB	Output is correct
26	Correct	114 ms	17920 KB	Output is correct
27	Correct	229 ms	19324 KB	Output is correct
28	Correct	456 ms	30552 KB	Output is correct
29	Correct	513 ms	30552 KB	Output is correct
30	Correct	215 ms	30552 KB	Output is correct
31	Correct	227 ms	30552 KB	Output is correct
32	Correct	288 ms	30552 KB	Output is correct
33	Correct	423 ms	30552 KB	Output is correct
34	Correct	395 ms	30552 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	4984 KB	Output is correct
2	Correct	6 ms	5220 KB	Output is correct
3	Correct	5 ms	5220 KB	Output is correct
4	Correct	5 ms	5220 KB	Output is correct
5	Correct	5 ms	5220 KB	Output is correct
6	Correct	6 ms	5296 KB	Output is correct
7	Correct	6 ms	5320 KB	Output is correct
8	Correct	5 ms	5336 KB	Output is correct
9	Correct	6 ms	5336 KB	Output is correct
10	Correct	6 ms	5336 KB	Output is correct
11	Correct	6 ms	5340 KB	Output is correct
12	Correct	5 ms	5340 KB	Output is correct
13	Correct	6 ms	5340 KB	Output is correct
14	Correct	5 ms	5340 KB	Output is correct
15	Correct	5 ms	5340 KB	Output is correct
16	Correct	5 ms	5372 KB	Output is correct
17	Correct	6 ms	5372 KB	Output is correct
18	Correct	6 ms	5372 KB	Output is correct
19	Correct	5 ms	5372 KB	Output is correct
20	Correct	5 ms	5372 KB	Output is correct
21	Correct	7 ms	5372 KB	Output is correct
22	Correct	14 ms	12156 KB	Output is correct
23	Correct	15 ms	12156 KB	Output is correct
24	Correct	16 ms	13692 KB	Output is correct
25	Correct	13 ms	13692 KB	Output is correct
26	Correct	10 ms	13692 KB	Output is correct
27	Correct	7 ms	13692 KB	Output is correct
28	Correct	9 ms	13692 KB	Output is correct
29	Correct	11 ms	13692 KB	Output is correct
30	Correct	12 ms	13692 KB	Output is correct
31	Correct	12 ms	13692 KB	Output is correct
32	Correct	14 ms	13692 KB	Output is correct
33	Correct	15 ms	14844 KB	Output is correct
34	Correct	16 ms	14844 KB	Output is correct
35	Correct	16 ms	15356 KB	Output is correct
36	Correct	17 ms	15996 KB	Output is correct
37	Correct	13 ms	15996 KB	Output is correct
38	Correct	10 ms	15996 KB	Output is correct
39	Correct	172 ms	15996 KB	Output is correct
40	Correct	164 ms	15996 KB	Output is correct
41	Correct	217 ms	15996 KB	Output is correct
42	Correct	220 ms	15996 KB	Output is correct
43	Correct	116 ms	15996 KB	Output is correct
44	Correct	77 ms	15996 KB	Output is correct
45	Correct	192 ms	15996 KB	Output is correct
46	Correct	114 ms	17920 KB	Output is correct
47	Correct	229 ms	19324 KB	Output is correct
48	Correct	456 ms	30552 KB	Output is correct
49	Correct	513 ms	30552 KB	Output is correct
50	Correct	215 ms	30552 KB	Output is correct
51	Correct	227 ms	30552 KB	Output is correct
52	Correct	288 ms	30552 KB	Output is correct
53	Correct	423 ms	30552 KB	Output is correct
54	Correct	395 ms	30552 KB	Output is correct
55	Correct	16 ms	30552 KB	Output is correct
56	Correct	19 ms	30552 KB	Output is correct
57	Correct	98 ms	30552 KB	Output is correct
58	Correct	53 ms	30552 KB	Output is correct
59	Correct	137 ms	30552 KB	Output is correct
60	Correct	803 ms	39424 KB	Output is correct
61	Correct	227 ms	39424 KB	Output is correct
62	Correct	255 ms	39424 KB	Output is correct
63	Correct	308 ms	39424 KB	Output is correct
64	Correct	700 ms	39424 KB	Output is correct
65	Correct	413 ms	39424 KB	Output is correct
66	Correct	916 ms	43224 KB	Output is correct
67	Correct	264 ms	43224 KB	Output is correct
68	Correct	418 ms	43224 KB	Output is correct
69	Correct	406 ms	43224 KB	Output is correct
70	Correct	327 ms	43224 KB	Output is correct

답안 #41188

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