답안 #820166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
820166	2023-08-10T22:15:27 Z	PenguinsAreCute	경주 (Race) (IOI11_race)	C++17	100 / 100	393 ms	106956 KB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define re first
#define im second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
#define MAXN 200069
#define INF 314159265358979323
int ans=INF,k;
vii adj[MAXN];
int lazy_dist[MAXN], lazy_highways[MAXN];
map<int,int> min_dist[MAXN];
void dfs(int x, int p) {
	min_dist[x][0]=0;
	for(auto i: adj[x]) if(i.re!=p) {
		dfs(i.re, x);
		lazy_dist[i.re]+=i.im;
		lazy_highways[i.re]++;
		if(min_dist[i.re].size()>min_dist[x].size()) {
			swap(min_dist[i.re], min_dist[x]);
			swap(lazy_dist[i.re], lazy_dist[x]);
			swap(lazy_highways[i.re], lazy_highways[x]);
		}
		for(auto it: min_dist[i.re]) {
			int rem=k-it.re-lazy_dist[i.re]-lazy_dist[x];
			if(min_dist[x].count(rem)) ans=min(ans, it.im+min_dist[x][rem]+lazy_highways[i.re]+lazy_highways[x]);
		}
		for(auto it: min_dist[i.re]) {
			int insPt=it.re+lazy_dist[i.re]-lazy_dist[x], insV=it.im+lazy_highways[i.re]-lazy_highways[x];
			if(min_dist[x].count(insPt)) min_dist[x][insPt]=min(min_dist[x][insPt],insV);
			else min_dist[x][insPt]=insV;
		}
	}
}
int32_t best_path(int32_t N, int32_t K, int32_t H[][2], int32_t L[]) {
	REP(i,0,N-1) {
		adj[H[i][0]].pb(ii(H[i][1],L[i]));
		adj[H[i][1]].pb(ii(H[i][0],L[i]));
	}
	k=K;
	dfs(0,-1);
	return ((ans==INF)?-1:ans);
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14420 KB	Output is correct
2	Correct	7 ms	14420 KB	Output is correct
3	Correct	7 ms	14416 KB	Output is correct
4	Correct	6 ms	14384 KB	Output is correct
5	Correct	6 ms	14420 KB	Output is correct
6	Correct	9 ms	14420 KB	Output is correct
7	Correct	6 ms	14420 KB	Output is correct
8	Correct	7 ms	14420 KB	Output is correct
9	Correct	8 ms	14360 KB	Output is correct
10	Correct	7 ms	14420 KB	Output is correct
11	Correct	7 ms	14424 KB	Output is correct
12	Correct	6 ms	14420 KB	Output is correct
13	Correct	8 ms	14372 KB	Output is correct
14	Correct	6 ms	14408 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	7 ms	14340 KB	Output is correct
17	Correct	7 ms	14420 KB	Output is correct
18	Correct	7 ms	14328 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14420 KB	Output is correct
2	Correct	7 ms	14420 KB	Output is correct
3	Correct	7 ms	14416 KB	Output is correct
4	Correct	6 ms	14384 KB	Output is correct
5	Correct	6 ms	14420 KB	Output is correct
6	Correct	9 ms	14420 KB	Output is correct
7	Correct	6 ms	14420 KB	Output is correct
8	Correct	7 ms	14420 KB	Output is correct
9	Correct	8 ms	14360 KB	Output is correct
10	Correct	7 ms	14420 KB	Output is correct
11	Correct	7 ms	14424 KB	Output is correct
12	Correct	6 ms	14420 KB	Output is correct
13	Correct	8 ms	14372 KB	Output is correct
14	Correct	6 ms	14408 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	7 ms	14340 KB	Output is correct
17	Correct	7 ms	14420 KB	Output is correct
18	Correct	7 ms	14328 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	6 ms	14420 KB	Output is correct
21	Correct	7 ms	14676 KB	Output is correct
22	Correct	8 ms	14676 KB	Output is correct
23	Correct	8 ms	14672 KB	Output is correct
24	Correct	8 ms	14676 KB	Output is correct
25	Correct	8 ms	14676 KB	Output is correct
26	Correct	9 ms	14676 KB	Output is correct
27	Correct	7 ms	14548 KB	Output is correct
28	Correct	8 ms	14676 KB	Output is correct
29	Correct	8 ms	14676 KB	Output is correct
30	Correct	8 ms	14676 KB	Output is correct
31	Correct	9 ms	14676 KB	Output is correct
32	Correct	8 ms	14676 KB	Output is correct
33	Correct	8 ms	14668 KB	Output is correct
34	Correct	9 ms	14676 KB	Output is correct
35	Correct	8 ms	14676 KB	Output is correct
36	Correct	7 ms	14672 KB	Output is correct
37	Correct	9 ms	14676 KB	Output is correct
38	Correct	9 ms	14680 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14420 KB	Output is correct
2	Correct	7 ms	14420 KB	Output is correct
3	Correct	7 ms	14416 KB	Output is correct
4	Correct	6 ms	14384 KB	Output is correct
5	Correct	6 ms	14420 KB	Output is correct
6	Correct	9 ms	14420 KB	Output is correct
7	Correct	6 ms	14420 KB	Output is correct
8	Correct	7 ms	14420 KB	Output is correct
9	Correct	8 ms	14360 KB	Output is correct
10	Correct	7 ms	14420 KB	Output is correct
11	Correct	7 ms	14424 KB	Output is correct
12	Correct	6 ms	14420 KB	Output is correct
13	Correct	8 ms	14372 KB	Output is correct
14	Correct	6 ms	14408 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	7 ms	14340 KB	Output is correct
17	Correct	7 ms	14420 KB	Output is correct
18	Correct	7 ms	14328 KB	Output is correct
19	Correct	100 ms	39172 KB	Output is correct
20	Correct	100 ms	39196 KB	Output is correct
21	Correct	107 ms	38904 KB	Output is correct
22	Correct	101 ms	38464 KB	Output is correct
23	Correct	148 ms	51472 KB	Output is correct
24	Correct	103 ms	41364 KB	Output is correct
25	Correct	89 ms	38276 KB	Output is correct
26	Correct	50 ms	45004 KB	Output is correct
27	Correct	152 ms	52596 KB	Output is correct
28	Correct	236 ms	88416 KB	Output is correct
29	Correct	236 ms	87064 KB	Output is correct
30	Correct	154 ms	52592 KB	Output is correct
31	Correct	168 ms	52548 KB	Output is correct
32	Correct	211 ms	52624 KB	Output is correct
33	Correct	215 ms	57356 KB	Output is correct
34	Correct	298 ms	89348 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14420 KB	Output is correct
2	Correct	7 ms	14420 KB	Output is correct
3	Correct	7 ms	14416 KB	Output is correct
4	Correct	6 ms	14384 KB	Output is correct
5	Correct	6 ms	14420 KB	Output is correct
6	Correct	9 ms	14420 KB	Output is correct
7	Correct	6 ms	14420 KB	Output is correct
8	Correct	7 ms	14420 KB	Output is correct
9	Correct	8 ms	14360 KB	Output is correct
10	Correct	7 ms	14420 KB	Output is correct
11	Correct	7 ms	14424 KB	Output is correct
12	Correct	6 ms	14420 KB	Output is correct
13	Correct	8 ms	14372 KB	Output is correct
14	Correct	6 ms	14408 KB	Output is correct
15	Correct	7 ms	14420 KB	Output is correct
16	Correct	7 ms	14340 KB	Output is correct
17	Correct	7 ms	14420 KB	Output is correct
18	Correct	7 ms	14328 KB	Output is correct
19	Correct	7 ms	14420 KB	Output is correct
20	Correct	6 ms	14420 KB	Output is correct
21	Correct	7 ms	14676 KB	Output is correct
22	Correct	8 ms	14676 KB	Output is correct
23	Correct	8 ms	14672 KB	Output is correct
24	Correct	8 ms	14676 KB	Output is correct
25	Correct	8 ms	14676 KB	Output is correct
26	Correct	9 ms	14676 KB	Output is correct
27	Correct	7 ms	14548 KB	Output is correct
28	Correct	8 ms	14676 KB	Output is correct
29	Correct	8 ms	14676 KB	Output is correct
30	Correct	8 ms	14676 KB	Output is correct
31	Correct	9 ms	14676 KB	Output is correct
32	Correct	8 ms	14676 KB	Output is correct
33	Correct	8 ms	14668 KB	Output is correct
34	Correct	9 ms	14676 KB	Output is correct
35	Correct	8 ms	14676 KB	Output is correct
36	Correct	7 ms	14672 KB	Output is correct
37	Correct	9 ms	14676 KB	Output is correct
38	Correct	9 ms	14680 KB	Output is correct
39	Correct	100 ms	39172 KB	Output is correct
40	Correct	100 ms	39196 KB	Output is correct
41	Correct	107 ms	38904 KB	Output is correct
42	Correct	101 ms	38464 KB	Output is correct
43	Correct	148 ms	51472 KB	Output is correct
44	Correct	103 ms	41364 KB	Output is correct
45	Correct	89 ms	38276 KB	Output is correct
46	Correct	50 ms	45004 KB	Output is correct
47	Correct	152 ms	52596 KB	Output is correct
48	Correct	236 ms	88416 KB	Output is correct
49	Correct	236 ms	87064 KB	Output is correct
50	Correct	154 ms	52592 KB	Output is correct
51	Correct	168 ms	52548 KB	Output is correct
52	Correct	211 ms	52624 KB	Output is correct
53	Correct	215 ms	57356 KB	Output is correct
54	Correct	298 ms	89348 KB	Output is correct
55	Correct	18 ms	17876 KB	Output is correct
56	Correct	12 ms	16508 KB	Output is correct
57	Correct	67 ms	36696 KB	Output is correct
58	Correct	55 ms	29060 KB	Output is correct
59	Correct	79 ms	51300 KB	Output is correct
60	Correct	256 ms	87508 KB	Output is correct
61	Correct	217 ms	56024 KB	Output is correct
62	Correct	157 ms	52608 KB	Output is correct
63	Correct	209 ms	52608 KB	Output is correct
64	Correct	393 ms	106956 KB	Output is correct
65	Correct	378 ms	104664 KB	Output is correct
66	Correct	283 ms	83868 KB	Output is correct
67	Correct	164 ms	44992 KB	Output is correct
68	Correct	295 ms	68336 KB	Output is correct
69	Correct	339 ms	73072 KB	Output is correct
70	Correct	291 ms	66068 KB	Output is correct

답안 #820166

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