답안 #976105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976105	2024-05-06T07:47:57 Z	Amaarsaa	경주 (Race) (IOI11_race)	C++14	100 / 100	309 ms	37540 KB

race

#include<bits/stdc++.h>
using namespace std;
#define MAX_N 500000
 
vector < pair < int, int > > adj[200004];
int sz[200004], used[200005] = {0}, d[1000004];
vector < int > v;
int k;
int find_size(int node, int parent) {
	sz[node] = 1;
	for ( pair <int,int >& A : adj[node]) {
		int child = A.first;
		if ( used[child] || parent == child) continue;
		sz[node] += find_size(child, node);
	}
	return sz[node];
}
int find_centroid(int node, int parent, int n) {
	for ( pair <int, int>& A : adj[node]) {
		int child = A.first;
		if ( child == parent || used[child] ) continue;
		if ( sz[child] * 2 > n) return find_centroid(child, node, n);
		
	}
	return node;
}
int ans = -1;
void dfs(int node, int parent, int budjaagaa, int dist, int depth) {
	if ( dist > k) return;
	if ( budjaagaa) {
		if ( d[dist] == -1) d[dist] = depth;
		else d[dist] = min(d[dist], depth);
		v.push_back(dist);
	}
	else {
		if ( d[k - dist] != -1) {
			if ( ans == -1) ans = depth + d[k - dist];
			else ans = min(ans, depth + d[k - dist]);
		}
	}
	for ( pair < int, int>&A : adj[node]) {
		int child = A.first;
		if ( used[child] || child == parent) continue;
		dfs(child, node, budjaagaa, dist + A.second, depth + 1);
	}
}
void solve(int node) {
	int c = find_centroid(node, node, find_size(node, node));
	used[c] = 1;
	v.clear();
	for ( pair <int, int>& A : adj[c]) {
		int child = A.first;
		if ( used[child]) continue;
		dfs(child, c, 0, A.second, 1);
		dfs(child, c, 1, A.second, 1);
	}
	for (int X : v) {
		d[X] = -1;
	}
	for ( pair <int, int>& A : adj[c]) {
		int child = A.first;
		if ( used[child]) continue;
		solve(child);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	k = K;
	for (int i = 0; i < (N - 1); i ++) {
		adj[H[i][0]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	for (int i = 0; i <=K; i ++) d[i] = -1;
	d[0]= 0;
	solve(0);
	
	return ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10072 KB	Output is correct
2	Correct	2 ms	10076 KB	Output is correct
3	Correct	3 ms	10076 KB	Output is correct
4	Correct	3 ms	10076 KB	Output is correct
5	Correct	2 ms	10076 KB	Output is correct
6	Correct	2 ms	10076 KB	Output is correct
7	Correct	2 ms	10072 KB	Output is correct
8	Correct	3 ms	10072 KB	Output is correct
9	Correct	2 ms	10072 KB	Output is correct
10	Correct	3 ms	10076 KB	Output is correct
11	Correct	3 ms	10076 KB	Output is correct
12	Correct	3 ms	10076 KB	Output is correct
13	Correct	3 ms	10076 KB	Output is correct
14	Correct	3 ms	10076 KB	Output is correct
15	Correct	2 ms	10076 KB	Output is correct
16	Correct	2 ms	10076 KB	Output is correct
17	Correct	2 ms	10076 KB	Output is correct
18	Correct	2 ms	10076 KB	Output is correct
19	Correct	2 ms	10076 KB	Output is correct
20	Correct	3 ms	10076 KB	Output is correct
21	Correct	3 ms	10076 KB	Output is correct
22	Correct	4 ms	14172 KB	Output is correct
23	Correct	4 ms	14172 KB	Output is correct
24	Correct	4 ms	14172 KB	Output is correct
25	Correct	4 ms	14172 KB	Output is correct
26	Correct	3 ms	12120 KB	Output is correct
27	Correct	3 ms	14172 KB	Output is correct
28	Correct	3 ms	12124 KB	Output is correct
29	Correct	3 ms	12124 KB	Output is correct
30	Correct	3 ms	12192 KB	Output is correct
31	Correct	4 ms	14172 KB	Output is correct
32	Correct	3 ms	14168 KB	Output is correct
33	Correct	3 ms	14252 KB	Output is correct
34	Correct	3 ms	12120 KB	Output is correct
35	Correct	4 ms	14172 KB	Output is correct
36	Correct	3 ms	14256 KB	Output is correct
37	Correct	3 ms	14172 KB	Output is correct
38	Correct	4 ms	12124 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10072 KB	Output is correct
2	Correct	2 ms	10076 KB	Output is correct
3	Correct	3 ms	10076 KB	Output is correct
4	Correct	3 ms	10076 KB	Output is correct
5	Correct	2 ms	10076 KB	Output is correct
6	Correct	2 ms	10076 KB	Output is correct
7	Correct	2 ms	10072 KB	Output is correct
8	Correct	3 ms	10072 KB	Output is correct
9	Correct	2 ms	10072 KB	Output is correct
10	Correct	3 ms	10076 KB	Output is correct
11	Correct	3 ms	10076 KB	Output is correct
12	Correct	3 ms	10076 KB	Output is correct
13	Correct	3 ms	10076 KB	Output is correct
14	Correct	3 ms	10076 KB	Output is correct
15	Correct	2 ms	10076 KB	Output is correct
16	Correct	2 ms	10076 KB	Output is correct
17	Correct	2 ms	10076 KB	Output is correct
18	Correct	2 ms	10076 KB	Output is correct
19	Correct	104 ms	16660 KB	Output is correct
20	Correct	78 ms	17488 KB	Output is correct
21	Correct	83 ms	17360 KB	Output is correct
22	Correct	76 ms	18180 KB	Output is correct
23	Correct	49 ms	18000 KB	Output is correct
24	Correct	38 ms	17744 KB	Output is correct
25	Correct	87 ms	20304 KB	Output is correct
26	Correct	69 ms	23428 KB	Output is correct
27	Correct	105 ms	22016 KB	Output is correct
28	Correct	222 ms	33432 KB	Output is correct
29	Correct	156 ms	32848 KB	Output is correct
30	Correct	101 ms	22772 KB	Output is correct
31	Correct	105 ms	22788 KB	Output is correct
32	Correct	120 ms	22612 KB	Output is correct
33	Correct	170 ms	21616 KB	Output is correct
34	Correct	105 ms	21840 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10072 KB	Output is correct
2	Correct	2 ms	10076 KB	Output is correct
3	Correct	3 ms	10076 KB	Output is correct
4	Correct	3 ms	10076 KB	Output is correct
5	Correct	2 ms	10076 KB	Output is correct
6	Correct	2 ms	10076 KB	Output is correct
7	Correct	2 ms	10072 KB	Output is correct
8	Correct	3 ms	10072 KB	Output is correct
9	Correct	2 ms	10072 KB	Output is correct
10	Correct	3 ms	10076 KB	Output is correct
11	Correct	3 ms	10076 KB	Output is correct
12	Correct	3 ms	10076 KB	Output is correct
13	Correct	3 ms	10076 KB	Output is correct
14	Correct	3 ms	10076 KB	Output is correct
15	Correct	2 ms	10076 KB	Output is correct
16	Correct	2 ms	10076 KB	Output is correct
17	Correct	2 ms	10076 KB	Output is correct
18	Correct	2 ms	10076 KB	Output is correct
19	Correct	2 ms	10076 KB	Output is correct
20	Correct	3 ms	10076 KB	Output is correct
21	Correct	3 ms	10076 KB	Output is correct
22	Correct	4 ms	14172 KB	Output is correct
23	Correct	4 ms	14172 KB	Output is correct
24	Correct	4 ms	14172 KB	Output is correct
25	Correct	4 ms	14172 KB	Output is correct
26	Correct	3 ms	12120 KB	Output is correct
27	Correct	3 ms	14172 KB	Output is correct
28	Correct	3 ms	12124 KB	Output is correct
29	Correct	3 ms	12124 KB	Output is correct
30	Correct	3 ms	12192 KB	Output is correct
31	Correct	4 ms	14172 KB	Output is correct
32	Correct	3 ms	14168 KB	Output is correct
33	Correct	3 ms	14252 KB	Output is correct
34	Correct	3 ms	12120 KB	Output is correct
35	Correct	4 ms	14172 KB	Output is correct
36	Correct	3 ms	14256 KB	Output is correct
37	Correct	3 ms	14172 KB	Output is correct
38	Correct	4 ms	12124 KB	Output is correct
39	Correct	104 ms	16660 KB	Output is correct
40	Correct	78 ms	17488 KB	Output is correct
41	Correct	83 ms	17360 KB	Output is correct
42	Correct	76 ms	18180 KB	Output is correct
43	Correct	49 ms	18000 KB	Output is correct
44	Correct	38 ms	17744 KB	Output is correct
45	Correct	87 ms	20304 KB	Output is correct
46	Correct	69 ms	23428 KB	Output is correct
47	Correct	105 ms	22016 KB	Output is correct
48	Correct	222 ms	33432 KB	Output is correct
49	Correct	156 ms	32848 KB	Output is correct
50	Correct	101 ms	22772 KB	Output is correct
51	Correct	105 ms	22788 KB	Output is correct
52	Correct	120 ms	22612 KB	Output is correct
53	Correct	170 ms	21616 KB	Output is correct
54	Correct	105 ms	21840 KB	Output is correct
55	Correct	9 ms	10620 KB	Output is correct
56	Correct	9 ms	10588 KB	Output is correct
57	Correct	55 ms	17296 KB	Output is correct
58	Correct	28 ms	18640 KB	Output is correct
59	Correct	74 ms	25552 KB	Output is correct
60	Correct	272 ms	37540 KB	Output is correct
61	Correct	126 ms	22152 KB	Output is correct
62	Correct	134 ms	27096 KB	Output is correct
63	Correct	157 ms	27256 KB	Output is correct
64	Correct	309 ms	24460 KB	Output is correct
65	Correct	137 ms	23436 KB	Output is correct
66	Correct	228 ms	32344 KB	Output is correct
67	Correct	88 ms	29376 KB	Output is correct
68	Correct	175 ms	27088 KB	Output is correct
69	Correct	160 ms	24952 KB	Output is correct
70	Correct	148 ms	27088 KB	Output is correct

답안 #976105

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