답안 #956057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
956057 2024-03-31T23:58:34 Z RadicaI 경주 (Race) (IOI11_race) C++17
100 / 100
346 ms 79440 KB
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
const int mx = 2e5+1;
#define F first
#define S second
vector<vector<pair<int,int>>> adj(mx);
map<int,int> arr[mx];
int ans=1e9;
void dfs(int node, int par, int dep, int depth, int k){
	for(auto x: adj[node])if(x.F != par){
		dfs(x.F, node, dep+1, depth + x.S, k);
		if(arr[x.F].size() > arr[node].size()) swap(arr[node], arr[x.F]);
		for(auto thing: arr[x.F])if(arr[node].count(k + 2 * depth - thing.F)) ans  = min(ans, arr[node][k+2*depth-thing.F]+thing.S - 2*dep);
		for(auto thing: arr[x.F]){
			if(arr[node].count(thing.F)) arr[node][thing.F] = min(arr[node][thing.F], thing.S);
			else arr[node][thing.F] = thing.S;
		}
	}
	if(arr[node].count(k + depth)) ans = min(ans, arr[node][k+depth] - dep);
	arr[node][depth] = dep;
}

int best_path(int n, int k, int h[][2], int l[]){
	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]});
	}
	dfs(0,0,0,0,k);
	return (ans == 1e9 ? -1 : ans);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18012 KB Output is correct
2 Correct 5 ms 18204 KB Output is correct
3 Correct 4 ms 18012 KB Output is correct
4 Correct 4 ms 18012 KB Output is correct
5 Correct 5 ms 18012 KB Output is correct
6 Correct 5 ms 18012 KB Output is correct
7 Correct 5 ms 18012 KB Output is correct
8 Correct 5 ms 18012 KB Output is correct
9 Correct 5 ms 18008 KB Output is correct
10 Correct 5 ms 18012 KB Output is correct
11 Correct 5 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18012 KB Output is correct
14 Correct 6 ms 18012 KB Output is correct
15 Correct 5 ms 17964 KB Output is correct
16 Correct 5 ms 18012 KB Output is correct
17 Correct 4 ms 18012 KB Output is correct
18 Correct 5 ms 17964 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18012 KB Output is correct
2 Correct 5 ms 18204 KB Output is correct
3 Correct 4 ms 18012 KB Output is correct
4 Correct 4 ms 18012 KB Output is correct
5 Correct 5 ms 18012 KB Output is correct
6 Correct 5 ms 18012 KB Output is correct
7 Correct 5 ms 18012 KB Output is correct
8 Correct 5 ms 18012 KB Output is correct
9 Correct 5 ms 18008 KB Output is correct
10 Correct 5 ms 18012 KB Output is correct
11 Correct 5 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18012 KB Output is correct
14 Correct 6 ms 18012 KB Output is correct
15 Correct 5 ms 17964 KB Output is correct
16 Correct 5 ms 18012 KB Output is correct
17 Correct 4 ms 18012 KB Output is correct
18 Correct 5 ms 17964 KB Output is correct
19 Correct 6 ms 18012 KB Output is correct
20 Correct 4 ms 18012 KB Output is correct
21 Correct 6 ms 18268 KB Output is correct
22 Correct 5 ms 18268 KB Output is correct
23 Correct 6 ms 18268 KB Output is correct
24 Correct 6 ms 18268 KB Output is correct
25 Correct 6 ms 18264 KB Output is correct
26 Correct 6 ms 18268 KB Output is correct
27 Correct 5 ms 18212 KB Output is correct
28 Correct 7 ms 18268 KB Output is correct
29 Correct 5 ms 18268 KB Output is correct
30 Correct 5 ms 18268 KB Output is correct
31 Correct 6 ms 18268 KB Output is correct
32 Correct 6 ms 18224 KB Output is correct
33 Correct 6 ms 18264 KB Output is correct
34 Correct 6 ms 18268 KB Output is correct
35 Correct 6 ms 18184 KB Output is correct
36 Correct 5 ms 18268 KB Output is correct
37 Correct 4 ms 18268 KB Output is correct
38 Correct 6 ms 18268 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18012 KB Output is correct
2 Correct 5 ms 18204 KB Output is correct
3 Correct 4 ms 18012 KB Output is correct
4 Correct 4 ms 18012 KB Output is correct
5 Correct 5 ms 18012 KB Output is correct
6 Correct 5 ms 18012 KB Output is correct
7 Correct 5 ms 18012 KB Output is correct
8 Correct 5 ms 18012 KB Output is correct
9 Correct 5 ms 18008 KB Output is correct
10 Correct 5 ms 18012 KB Output is correct
11 Correct 5 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18012 KB Output is correct
14 Correct 6 ms 18012 KB Output is correct
15 Correct 5 ms 17964 KB Output is correct
16 Correct 5 ms 18012 KB Output is correct
17 Correct 4 ms 18012 KB Output is correct
18 Correct 5 ms 17964 KB Output is correct
19 Correct 81 ms 32440 KB Output is correct
20 Correct 83 ms 33360 KB Output is correct
21 Correct 77 ms 33104 KB Output is correct
22 Correct 83 ms 33872 KB Output is correct
23 Correct 116 ms 43604 KB Output is correct
24 Correct 96 ms 38428 KB Output is correct
25 Correct 63 ms 33532 KB Output is correct
26 Correct 43 ms 39796 KB Output is correct
27 Correct 142 ms 38996 KB Output is correct
28 Correct 160 ms 68716 KB Output is correct
29 Correct 159 ms 67440 KB Output is correct
30 Correct 138 ms 39764 KB Output is correct
31 Correct 134 ms 39760 KB Output is correct
32 Correct 179 ms 39748 KB Output is correct
33 Correct 147 ms 38484 KB Output is correct
34 Correct 239 ms 62808 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 18012 KB Output is correct
2 Correct 5 ms 18204 KB Output is correct
3 Correct 4 ms 18012 KB Output is correct
4 Correct 4 ms 18012 KB Output is correct
5 Correct 5 ms 18012 KB Output is correct
6 Correct 5 ms 18012 KB Output is correct
7 Correct 5 ms 18012 KB Output is correct
8 Correct 5 ms 18012 KB Output is correct
9 Correct 5 ms 18008 KB Output is correct
10 Correct 5 ms 18012 KB Output is correct
11 Correct 5 ms 18012 KB Output is correct
12 Correct 4 ms 18012 KB Output is correct
13 Correct 4 ms 18012 KB Output is correct
14 Correct 6 ms 18012 KB Output is correct
15 Correct 5 ms 17964 KB Output is correct
16 Correct 5 ms 18012 KB Output is correct
17 Correct 4 ms 18012 KB Output is correct
18 Correct 5 ms 17964 KB Output is correct
19 Correct 6 ms 18012 KB Output is correct
20 Correct 4 ms 18012 KB Output is correct
21 Correct 6 ms 18268 KB Output is correct
22 Correct 5 ms 18268 KB Output is correct
23 Correct 6 ms 18268 KB Output is correct
24 Correct 6 ms 18268 KB Output is correct
25 Correct 6 ms 18264 KB Output is correct
26 Correct 6 ms 18268 KB Output is correct
27 Correct 5 ms 18212 KB Output is correct
28 Correct 7 ms 18268 KB Output is correct
29 Correct 5 ms 18268 KB Output is correct
30 Correct 5 ms 18268 KB Output is correct
31 Correct 6 ms 18268 KB Output is correct
32 Correct 6 ms 18224 KB Output is correct
33 Correct 6 ms 18264 KB Output is correct
34 Correct 6 ms 18268 KB Output is correct
35 Correct 6 ms 18184 KB Output is correct
36 Correct 5 ms 18268 KB Output is correct
37 Correct 4 ms 18268 KB Output is correct
38 Correct 6 ms 18268 KB Output is correct
39 Correct 81 ms 32440 KB Output is correct
40 Correct 83 ms 33360 KB Output is correct
41 Correct 77 ms 33104 KB Output is correct
42 Correct 83 ms 33872 KB Output is correct
43 Correct 116 ms 43604 KB Output is correct
44 Correct 96 ms 38428 KB Output is correct
45 Correct 63 ms 33532 KB Output is correct
46 Correct 43 ms 39796 KB Output is correct
47 Correct 142 ms 38996 KB Output is correct
48 Correct 160 ms 68716 KB Output is correct
49 Correct 159 ms 67440 KB Output is correct
50 Correct 138 ms 39764 KB Output is correct
51 Correct 134 ms 39760 KB Output is correct
52 Correct 179 ms 39748 KB Output is correct
53 Correct 147 ms 38484 KB Output is correct
54 Correct 239 ms 62808 KB Output is correct
55 Correct 14 ms 20316 KB Output is correct
56 Correct 13 ms 19036 KB Output is correct
57 Correct 48 ms 31236 KB Output is correct
58 Correct 43 ms 29952 KB Output is correct
59 Correct 58 ms 44624 KB Output is correct
60 Correct 149 ms 68024 KB Output is correct
61 Correct 176 ms 41580 KB Output is correct
62 Correct 134 ms 39508 KB Output is correct
63 Correct 165 ms 39536 KB Output is correct
64 Correct 346 ms 77804 KB Output is correct
65 Correct 328 ms 79440 KB Output is correct
66 Correct 165 ms 62076 KB Output is correct
67 Correct 128 ms 40820 KB Output is correct
68 Correct 257 ms 53588 KB Output is correct
69 Correct 279 ms 55452 KB Output is correct
70 Correct 234 ms 52832 KB Output is correct