Submission #788021

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
788021	2023-07-19T16:26:19 Z	allin27x	Dreaming (IOI13_dreaming)	C++17	47 / 100	202 ms	49052 KB

dreaming

#include <bits/stdc++.h>
using namespace std;
#include "dreaming.h"
#define int long long

int ds[2][(int)1e5];
unordered_map<int,int> adj[(int)1e5];
int vis[(int)1e5];
int ind = 0;
unordered_set<int> sets[(int)1e5];
int cp[(int)1e5];

void dfs(int i , int p, int len, int x){
	sets[ind].insert(i);
	vis[i] = 1;
	ds[x][i] = len;
	for (auto const &pair: adj[i]){
		int c = pair.first; int w= pair.second;
		if (c==p) continue;
		dfs(c,i, len+w,x);
	}
}

signed travelTime(signed N, signed M, signed L, signed A[], signed B[], signed T[]){
	for (int i=0; i<M; i++){
		int a = A[i]; int b = B[i];
		adj[a][b] = T[i]; adj[b][a] = T[i];
	}
	int ans1 = 0 ;
	for (int i=0; i<N; i++) vis[i] = 0;
	for (int i=0; i<N; i++){
		if (vis[i]) continue;
		dfs(i,i,0,0);
		int a1 = i;
		for (auto c: sets[ind]){
			if (ds[0][c]>ds[0][a1]) a1 = c;
		}
		dfs(a1,a1,0,0);
		int a2 = a1;
		for (auto c: sets[ind]){
			if (ds[0][c]>ds[0][a2]) a2 = c;
		}
		dfs(a2,a2,0,1);
		int ans = 1e7;
		for (auto c: sets[ind]){
			ans = min(ans, max(ds[0][c], ds[1][c]));
		}
		ans1 = max(ans1, ds[1][a1]);
		cp[ind] = ans; 
		ind++;
	}
	if (ind == 1){
		ans1;
	}
	sort(cp, cp+ind);
	if (ind == 2) return max(ans1, L + cp[ind-1] +  cp[ind-2]);
	return max(ans1, max(L + cp[ind-1] + cp[ind-2], 2*L + cp[ind-2] + cp[ind-3]));
}

// signed main(){
// 	signed n = 10, m = 8 ;
// 	signed l = 2;
// 	signed a[] = {1, 2, 3, 4, 5, 6, 7, 8};
// 	signed b[] = {2, 3, 4, 5, 6, 7, 8, 9};
// 	signed t[] = {4, 2, 4, 3, 7, 1, 5, 3};
// 	cout<<travelTime(n,m,l,a,b,t);
// }

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:53:3: warning: statement has no effect [-Wunused-value]
   53 |   ans1;
      |   ^~~~

Subtask #1
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	44352 KB	Output is correct
2	Correct	114 ms	45556 KB	Output is correct
3	Correct	70 ms	33592 KB	Output is correct
4	Correct	16 ms	16340 KB	Output is correct
5	Correct	13 ms	14420 KB	Output is correct
6	Correct	23 ms	18684 KB	Output is correct
7	Correct	6 ms	11348 KB	Output is correct
8	Correct	42 ms	24456 KB	Output is correct
9	Correct	60 ms	28708 KB	Output is correct
10	Correct	6 ms	11476 KB	Output is correct
11	Correct	111 ms	35432 KB	Output is correct
12	Correct	128 ms	39872 KB	Output is correct
13	Correct	6 ms	11544 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11220 KB	Output is correct
2	Correct	6 ms	11252 KB	Output is correct
3	Correct	6 ms	11220 KB	Output is correct
4	Correct	6 ms	11220 KB	Output is correct
5	Correct	5 ms	11220 KB	Output is correct
6	Correct	6 ms	11324 KB	Output is correct
7	Correct	7 ms	11288 KB	Output is correct
8	Correct	6 ms	11220 KB	Output is correct
9	Correct	6 ms	11284 KB	Output is correct
10	Correct	6 ms	11220 KB	Output is correct
11	Correct	7 ms	11280 KB	Output is correct
12	Correct	7 ms	11216 KB	Output is correct
13	Correct	7 ms	11268 KB	Output is correct
14	Correct	6 ms	11220 KB	Output is correct
15	Correct	6 ms	11220 KB	Output is correct
16	Correct	6 ms	11280 KB	Output is correct
17	Correct	6 ms	11220 KB	Output is correct
18	Correct	7 ms	11280 KB	Output is correct
19	Correct	6 ms	11220 KB	Output is correct
20	Correct	6 ms	11288 KB	Output is correct
21	Correct	6 ms	11220 KB	Output is correct
22	Correct	6 ms	11220 KB	Output is correct
23	Correct	6 ms	11220 KB	Output is correct
24	Correct	6 ms	11284 KB	Output is correct
25	Correct	8 ms	11256 KB	Output is correct

Subtask #3
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	44352 KB	Output is correct
2	Correct	114 ms	45556 KB	Output is correct
3	Correct	70 ms	33592 KB	Output is correct
4	Correct	16 ms	16340 KB	Output is correct
5	Correct	13 ms	14420 KB	Output is correct
6	Correct	23 ms	18684 KB	Output is correct
7	Correct	6 ms	11348 KB	Output is correct
8	Correct	42 ms	24456 KB	Output is correct
9	Correct	60 ms	28708 KB	Output is correct
10	Correct	6 ms	11476 KB	Output is correct
11	Correct	111 ms	35432 KB	Output is correct
12	Correct	128 ms	39872 KB	Output is correct
13	Correct	6 ms	11544 KB	Output is correct
14	Correct	5 ms	11220 KB	Output is correct
15	Correct	6 ms	11252 KB	Output is correct
16	Correct	6 ms	11220 KB	Output is correct
17	Correct	6 ms	11220 KB	Output is correct
18	Correct	5 ms	11220 KB	Output is correct
19	Correct	6 ms	11324 KB	Output is correct
20	Correct	7 ms	11288 KB	Output is correct
21	Correct	6 ms	11220 KB	Output is correct
22	Correct	6 ms	11284 KB	Output is correct
23	Correct	6 ms	11220 KB	Output is correct
24	Correct	7 ms	11280 KB	Output is correct
25	Correct	7 ms	11216 KB	Output is correct
26	Correct	7 ms	11268 KB	Output is correct
27	Correct	6 ms	11220 KB	Output is correct
28	Correct	6 ms	11220 KB	Output is correct
29	Correct	6 ms	11280 KB	Output is correct
30	Correct	6 ms	11220 KB	Output is correct
31	Correct	7 ms	11280 KB	Output is correct
32	Correct	6 ms	11220 KB	Output is correct
33	Correct	6 ms	11288 KB	Output is correct
34	Correct	6 ms	11220 KB	Output is correct
35	Correct	6 ms	11220 KB	Output is correct
36	Correct	6 ms	11220 KB	Output is correct
37	Correct	6 ms	11284 KB	Output is correct
38	Correct	8 ms	11256 KB	Output is correct
39	Correct	107 ms	45532 KB	Output is correct
40	Correct	113 ms	45444 KB	Output is correct
41	Correct	71 ms	33628 KB	Output is correct
42	Correct	19 ms	16212 KB	Output is correct
43	Correct	7 ms	11284 KB	Output is correct
44	Correct	6 ms	11220 KB	Output is correct
45	Correct	6 ms	11220 KB	Output is correct
46	Correct	8 ms	11280 KB	Output is correct
47	Correct	6 ms	11220 KB	Output is correct
48	Correct	6 ms	11288 KB	Output is correct
49	Correct	6 ms	11272 KB	Output is correct
50	Correct	5 ms	11220 KB	Output is correct
51	Correct	6 ms	11220 KB	Output is correct
52	Correct	6 ms	11220 KB	Output is correct
53	Correct	6 ms	11268 KB	Output is correct
54	Correct	7 ms	11220 KB	Output is correct
55	Correct	6 ms	11220 KB	Output is correct
56	Correct	6 ms	11272 KB	Output is correct
57	Correct	202 ms	37912 KB	Output is correct
58	Correct	167 ms	38052 KB	Output is correct
59	Correct	169 ms	38132 KB	Output is correct
60	Correct	138 ms	38108 KB	Output is correct
61	Correct	141 ms	38180 KB	Output is correct
62	Correct	147 ms	37696 KB	Output is correct
63	Correct	153 ms	37824 KB	Output is correct
64	Correct	143 ms	37844 KB	Output is correct
65	Correct	144 ms	38032 KB	Output is correct
66	Correct	140 ms	38084 KB	Output is correct
67	Correct	142 ms	38144 KB	Output is correct
68	Correct	147 ms	38088 KB	Output is correct
69	Correct	190 ms	37940 KB	Output is correct
70	Correct	139 ms	38496 KB	Output is correct
71	Correct	6 ms	11220 KB	Output is correct
72	Correct	7 ms	11988 KB	Output is correct
73	Correct	8 ms	12016 KB	Output is correct
74	Correct	7 ms	11972 KB	Output is correct
75	Correct	7 ms	12108 KB	Output is correct
76	Correct	7 ms	12060 KB	Output is correct
77	Correct	8 ms	11988 KB	Output is correct
78	Correct	8 ms	11988 KB	Output is correct
79	Correct	7 ms	12068 KB	Output is correct
80	Correct	155 ms	37580 KB	Output is correct
81	Correct	159 ms	37612 KB	Output is correct
82	Correct	142 ms	38140 KB	Output is correct
83	Correct	133 ms	38088 KB	Output is correct
84	Correct	8 ms	11932 KB	Output is correct
85	Correct	7 ms	11840 KB	Output is correct
86	Correct	7 ms	11860 KB	Output is correct
87	Correct	7 ms	11932 KB	Output is correct
88	Correct	7 ms	11988 KB	Output is correct
89	Correct	7 ms	11988 KB	Output is correct
90	Correct	8 ms	11988 KB	Output is correct
91	Correct	8 ms	11976 KB	Output is correct
92	Correct	9 ms	11968 KB	Output is correct
93	Correct	9 ms	11920 KB	Output is correct
94	Correct	6 ms	11280 KB	Output is correct
95	Correct	6 ms	11220 KB	Output is correct
96	Correct	5 ms	11220 KB	Output is correct
97	Correct	6 ms	11280 KB	Output is correct
98	Correct	6 ms	11280 KB	Output is correct
99	Correct	6 ms	11220 KB	Output is correct
100	Correct	6 ms	11220 KB	Output is correct
101	Correct	5 ms	11220 KB	Output is correct
102	Correct	6 ms	11220 KB	Output is correct
103	Correct	7 ms	11220 KB	Output is correct
104	Correct	15 ms	14372 KB	Output is correct
105	Correct	22 ms	18644 KB	Output is correct
106	Correct	6 ms	11348 KB	Output is correct
107	Correct	42 ms	24448 KB	Output is correct
108	Correct	60 ms	28672 KB	Output is correct
109	Correct	6 ms	11476 KB	Output is correct
110	Correct	128 ms	35420 KB	Output is correct
111	Correct	120 ms	39876 KB	Output is correct
112	Correct	6 ms	11544 KB	Output is correct
113	Correct	184 ms	49052 KB	Output is correct

Subtask #4
0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	32816 KB	Output is correct
2	Correct	46 ms	33004 KB	Output is correct
3	Correct	52 ms	32852 KB	Output is correct
4	Correct	47 ms	32972 KB	Output is correct
5	Correct	48 ms	32716 KB	Output is correct
6	Correct	51 ms	34148 KB	Output is correct
7	Correct	51 ms	33832 KB	Output is correct
8	Correct	46 ms	32468 KB	Output is correct
9	Correct	45 ms	32332 KB	Output is correct
10	Correct	49 ms	33656 KB	Output is correct
11	Correct	6 ms	11220 KB	Output is correct
12	Correct	23 ms	28464 KB	Output is correct
13	Correct	23 ms	28500 KB	Output is correct
14	Correct	23 ms	28496 KB	Output is correct
15	Correct	22 ms	28492 KB	Output is correct
16	Correct	28 ms	28504 KB	Output is correct
17	Correct	22 ms	28500 KB	Output is correct
18	Correct	24 ms	28500 KB	Output is correct
19	Correct	24 ms	28508 KB	Output is correct
20	Incorrect	6 ms	11220 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	11220 KB	Output is correct
2	Correct	6 ms	11252 KB	Output is correct
3	Correct	6 ms	11220 KB	Output is correct
4	Correct	6 ms	11220 KB	Output is correct
5	Correct	5 ms	11220 KB	Output is correct
6	Correct	6 ms	11324 KB	Output is correct
7	Correct	7 ms	11288 KB	Output is correct
8	Correct	6 ms	11220 KB	Output is correct
9	Correct	6 ms	11284 KB	Output is correct
10	Correct	6 ms	11220 KB	Output is correct
11	Correct	7 ms	11280 KB	Output is correct
12	Correct	7 ms	11216 KB	Output is correct
13	Correct	7 ms	11268 KB	Output is correct
14	Correct	6 ms	11220 KB	Output is correct
15	Correct	6 ms	11220 KB	Output is correct
16	Correct	6 ms	11280 KB	Output is correct
17	Correct	6 ms	11220 KB	Output is correct
18	Correct	7 ms	11280 KB	Output is correct
19	Correct	6 ms	11220 KB	Output is correct
20	Correct	6 ms	11288 KB	Output is correct
21	Correct	6 ms	11220 KB	Output is correct
22	Correct	6 ms	11220 KB	Output is correct
23	Correct	6 ms	11220 KB	Output is correct
24	Correct	6 ms	11284 KB	Output is correct
25	Correct	8 ms	11256 KB	Output is correct
26	Correct	7 ms	11476 KB	Output is correct
27	Correct	7 ms	11740 KB	Output is correct
28	Correct	7 ms	11988 KB	Output is correct
29	Correct	6 ms	11476 KB	Output is correct
30	Correct	7 ms	11808 KB	Output is correct
31	Correct	8 ms	11968 KB	Output is correct
32	Correct	7 ms	11476 KB	Output is correct
33	Correct	7 ms	11812 KB	Output is correct
34	Correct	8 ms	12064 KB	Output is correct
35	Correct	5 ms	11220 KB	Output is correct
36	Correct	7 ms	11220 KB	Output is correct
37	Correct	7 ms	11220 KB	Output is correct
38	Correct	6 ms	11284 KB	Output is correct
39	Correct	6 ms	11220 KB	Output is correct
40	Correct	5 ms	11220 KB	Output is correct
41	Correct	6 ms	11252 KB	Output is correct
42	Correct	6 ms	11280 KB	Output is correct
43	Correct	6 ms	11280 KB	Output is correct
44	Correct	6 ms	11220 KB	Output is correct
45	Correct	5 ms	11220 KB	Output is correct
46	Correct	7 ms	11220 KB	Output is correct
47	Correct	8 ms	11288 KB	Output is correct
48	Correct	7 ms	11220 KB	Output is correct
49	Correct	6 ms	11208 KB	Output is correct
50	Correct	6 ms	11284 KB	Output is correct
51	Correct	6 ms	11348 KB	Output is correct
52	Incorrect	6 ms	11220 KB	Output isn't correct
53	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	119 ms	44352 KB	Output is correct
2	Correct	114 ms	45556 KB	Output is correct
3	Correct	70 ms	33592 KB	Output is correct
4	Correct	16 ms	16340 KB	Output is correct
5	Correct	13 ms	14420 KB	Output is correct
6	Correct	23 ms	18684 KB	Output is correct
7	Correct	6 ms	11348 KB	Output is correct
8	Correct	42 ms	24456 KB	Output is correct
9	Correct	60 ms	28708 KB	Output is correct
10	Correct	6 ms	11476 KB	Output is correct
11	Correct	111 ms	35432 KB	Output is correct
12	Correct	128 ms	39872 KB	Output is correct
13	Correct	6 ms	11544 KB	Output is correct
14	Correct	5 ms	11220 KB	Output is correct
15	Correct	6 ms	11252 KB	Output is correct
16	Correct	6 ms	11220 KB	Output is correct
17	Correct	6 ms	11220 KB	Output is correct
18	Correct	5 ms	11220 KB	Output is correct
19	Correct	6 ms	11324 KB	Output is correct
20	Correct	7 ms	11288 KB	Output is correct
21	Correct	6 ms	11220 KB	Output is correct
22	Correct	6 ms	11284 KB	Output is correct
23	Correct	6 ms	11220 KB	Output is correct
24	Correct	7 ms	11280 KB	Output is correct
25	Correct	7 ms	11216 KB	Output is correct
26	Correct	7 ms	11268 KB	Output is correct
27	Correct	6 ms	11220 KB	Output is correct
28	Correct	6 ms	11220 KB	Output is correct
29	Correct	6 ms	11280 KB	Output is correct
30	Correct	6 ms	11220 KB	Output is correct
31	Correct	7 ms	11280 KB	Output is correct
32	Correct	6 ms	11220 KB	Output is correct
33	Correct	6 ms	11288 KB	Output is correct
34	Correct	6 ms	11220 KB	Output is correct
35	Correct	6 ms	11220 KB	Output is correct
36	Correct	6 ms	11220 KB	Output is correct
37	Correct	6 ms	11284 KB	Output is correct
38	Correct	8 ms	11256 KB	Output is correct
39	Correct	107 ms	45532 KB	Output is correct
40	Correct	113 ms	45444 KB	Output is correct
41	Correct	71 ms	33628 KB	Output is correct
42	Correct	19 ms	16212 KB	Output is correct
43	Correct	7 ms	11284 KB	Output is correct
44	Correct	6 ms	11220 KB	Output is correct
45	Correct	6 ms	11220 KB	Output is correct
46	Correct	8 ms	11280 KB	Output is correct
47	Correct	6 ms	11220 KB	Output is correct
48	Correct	6 ms	11288 KB	Output is correct
49	Correct	6 ms	11272 KB	Output is correct
50	Correct	5 ms	11220 KB	Output is correct
51	Correct	6 ms	11220 KB	Output is correct
52	Correct	6 ms	11220 KB	Output is correct
53	Correct	6 ms	11268 KB	Output is correct
54	Correct	7 ms	11220 KB	Output is correct
55	Correct	6 ms	11220 KB	Output is correct
56	Correct	6 ms	11272 KB	Output is correct
57	Correct	202 ms	37912 KB	Output is correct
58	Correct	167 ms	38052 KB	Output is correct
59	Correct	169 ms	38132 KB	Output is correct
60	Correct	138 ms	38108 KB	Output is correct
61	Correct	141 ms	38180 KB	Output is correct
62	Correct	147 ms	37696 KB	Output is correct
63	Correct	153 ms	37824 KB	Output is correct
64	Correct	143 ms	37844 KB	Output is correct
65	Correct	144 ms	38032 KB	Output is correct
66	Correct	140 ms	38084 KB	Output is correct
67	Correct	142 ms	38144 KB	Output is correct
68	Correct	147 ms	38088 KB	Output is correct
69	Correct	190 ms	37940 KB	Output is correct
70	Correct	139 ms	38496 KB	Output is correct
71	Correct	6 ms	11220 KB	Output is correct
72	Correct	7 ms	11988 KB	Output is correct
73	Correct	8 ms	12016 KB	Output is correct
74	Correct	7 ms	11972 KB	Output is correct
75	Correct	7 ms	12108 KB	Output is correct
76	Correct	7 ms	12060 KB	Output is correct
77	Correct	8 ms	11988 KB	Output is correct
78	Correct	8 ms	11988 KB	Output is correct
79	Correct	7 ms	12068 KB	Output is correct
80	Correct	155 ms	37580 KB	Output is correct
81	Correct	159 ms	37612 KB	Output is correct
82	Correct	142 ms	38140 KB	Output is correct
83	Correct	133 ms	38088 KB	Output is correct
84	Correct	8 ms	11932 KB	Output is correct
85	Correct	7 ms	11840 KB	Output is correct
86	Correct	7 ms	11860 KB	Output is correct
87	Correct	7 ms	11932 KB	Output is correct
88	Correct	7 ms	11988 KB	Output is correct
89	Correct	7 ms	11988 KB	Output is correct
90	Correct	8 ms	11988 KB	Output is correct
91	Correct	8 ms	11976 KB	Output is correct
92	Correct	9 ms	11968 KB	Output is correct
93	Correct	9 ms	11920 KB	Output is correct
94	Correct	6 ms	11280 KB	Output is correct
95	Correct	6 ms	11220 KB	Output is correct
96	Correct	5 ms	11220 KB	Output is correct
97	Correct	6 ms	11280 KB	Output is correct
98	Correct	6 ms	11280 KB	Output is correct
99	Correct	6 ms	11220 KB	Output is correct
100	Correct	6 ms	11220 KB	Output is correct
101	Correct	5 ms	11220 KB	Output is correct
102	Correct	6 ms	11220 KB	Output is correct
103	Correct	7 ms	11220 KB	Output is correct
104	Correct	15 ms	14372 KB	Output is correct
105	Correct	22 ms	18644 KB	Output is correct
106	Correct	6 ms	11348 KB	Output is correct
107	Correct	42 ms	24448 KB	Output is correct
108	Correct	60 ms	28672 KB	Output is correct
109	Correct	6 ms	11476 KB	Output is correct
110	Correct	128 ms	35420 KB	Output is correct
111	Correct	120 ms	39876 KB	Output is correct
112	Correct	6 ms	11544 KB	Output is correct
113	Correct	184 ms	49052 KB	Output is correct
114	Correct	45 ms	32816 KB	Output is correct
115	Correct	46 ms	33004 KB	Output is correct
116	Correct	52 ms	32852 KB	Output is correct
117	Correct	47 ms	32972 KB	Output is correct
118	Correct	48 ms	32716 KB	Output is correct
119	Correct	51 ms	34148 KB	Output is correct
120	Correct	51 ms	33832 KB	Output is correct
121	Correct	46 ms	32468 KB	Output is correct
122	Correct	45 ms	32332 KB	Output is correct
123	Correct	49 ms	33656 KB	Output is correct
124	Correct	6 ms	11220 KB	Output is correct
125	Correct	23 ms	28464 KB	Output is correct
126	Correct	23 ms	28500 KB	Output is correct
127	Correct	23 ms	28496 KB	Output is correct
128	Correct	22 ms	28492 KB	Output is correct
129	Correct	28 ms	28504 KB	Output is correct
130	Correct	22 ms	28500 KB	Output is correct
131	Correct	24 ms	28500 KB	Output is correct
132	Correct	24 ms	28508 KB	Output is correct
133	Incorrect	6 ms	11220 KB	Output isn't correct
134	Halted	0 ms	0 KB	-

Submission #788021

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 10.0 / 10.0

Subtask #3 23.0 / 23.0

Subtask #4 0 / 18.0

Subtask #5 0 / 12.0

Subtask #6 0 / 23.0

Subtask #1
14.0 / 14.0

Subtask #2
10.0 / 10.0

Subtask #3
23.0 / 23.0

Subtask #4
0 / 18.0

Subtask #5
0 / 12.0

Subtask #6
0 / 23.0