답안 #208161

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208161	2020-03-10T06:39:35 Z	E869120	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2606 ms	266744 KB

amusementpark

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#pragma warning (disable: 4996)

int mod = 998244353;
int N, M, A[1009], B[1009];
int dp[387420489], power3[19], col[19];
vector<int> X[1009];

int main() {
	cin >> N >> M;
	for (int i = 1; i <= M; i++) { cin >> A[i] >> B[i]; A[i]--; B[i]--; }
	for (int i = 1; i <= M; i++) { X[A[i]].push_back(B[i]); X[B[i]].push_back(A[i]); }
	
	power3[0] = 1;
	for (int i = 1; i <= N; i++) power3[i] = 3LL * power3[i - 1];
	for (int i = 0; i < N; i++) {
		int ret = 2 * power3[i];
		for (int j = i + 1; j < N; j++) ret += power3[j];
		for (int j : X[i]) { if (j < i) ret += power3[j]; }
		dp[ret] = 1;
	}

	for (int i = 0; i < power3[N]; i++) {
		if (dp[i] == 0) continue;

		int val = 0;
		for (int j = 0; j < N; j++) col[j] = (i / power3[j]) % 3;
		for (int j = 0; j < N; j++) {
			if (col[j] != 1) continue;
			int ret = i + power3[j] - val;
			for (int k : X[j]) { if ((col[k] == 1 && k < j) || col[k] == 0) ret += power3[k]; }
			dp[ret] += dp[i]; val += power3[j];
			if (dp[ret] >= mod) dp[ret] -= mod;
		}
	}

	long long val = dp[power3[N] - 1];
	val *= M; val %= mod;
	if (val % 2 == 1) val += mod; val /= 2LL;
	cout << val << endl;
	return 0;
}

Compilation message

amusementpark.cpp:5:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
amusementpark.cpp: In function 'int main()':
amusementpark.cpp:42:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (val % 2 == 1) val += mod; val /= 2LL;
  ^~
amusementpark.cpp:42:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (val % 2 == 1) val += mod; val /= 2LL;
                                ^~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	5 ms	380 KB	Output is correct

Subtask #3
23.0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	5 ms	380 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Correct	5 ms	376 KB	Output is correct
28	Correct	5 ms	380 KB	Output is correct
29	Correct	5 ms	552 KB	Output is correct
30	Correct	5 ms	376 KB	Output is correct
31	Correct	5 ms	376 KB	Output is correct
32	Correct	5 ms	376 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	5 ms	376 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	5 ms	376 KB	Output is correct
37	Correct	5 ms	376 KB	Output is correct
38	Correct	5 ms	376 KB	Output is correct
39	Correct	5 ms	376 KB	Output is correct
40	Correct	5 ms	376 KB	Output is correct
41	Correct	5 ms	376 KB	Output is correct
42	Correct	5 ms	376 KB	Output is correct
43	Correct	5 ms	376 KB	Output is correct
44	Correct	5 ms	376 KB	Output is correct
45	Correct	5 ms	376 KB	Output is correct
46	Correct	5 ms	376 KB	Output is correct
47	Correct	5 ms	376 KB	Output is correct
48	Correct	5 ms	376 KB	Output is correct
49	Correct	5 ms	376 KB	Output is correct
50	Correct	5 ms	376 KB	Output is correct
51	Correct	5 ms	376 KB	Output is correct
52	Correct	5 ms	376 KB	Output is correct
53	Correct	5 ms	504 KB	Output is correct
54	Correct	5 ms	504 KB	Output is correct
55	Correct	5 ms	376 KB	Output is correct
56	Correct	6 ms	504 KB	Output is correct
57	Correct	6 ms	504 KB	Output is correct
58	Correct	6 ms	376 KB	Output is correct
59	Correct	5 ms	376 KB	Output is correct
60	Correct	5 ms	376 KB	Output is correct
61	Correct	5 ms	504 KB	Output is correct
62	Correct	5 ms	504 KB	Output is correct
63	Correct	5 ms	376 KB	Output is correct
64	Correct	5 ms	376 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	5 ms	380 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Correct	5 ms	376 KB	Output is correct
28	Correct	5 ms	380 KB	Output is correct
29	Correct	5 ms	552 KB	Output is correct
30	Correct	5 ms	376 KB	Output is correct
31	Correct	5 ms	376 KB	Output is correct
32	Correct	5 ms	376 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	5 ms	376 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	5 ms	376 KB	Output is correct
37	Correct	5 ms	376 KB	Output is correct
38	Correct	5 ms	376 KB	Output is correct
39	Correct	5 ms	376 KB	Output is correct
40	Correct	5 ms	376 KB	Output is correct
41	Correct	5 ms	376 KB	Output is correct
42	Correct	5 ms	376 KB	Output is correct
43	Correct	5 ms	376 KB	Output is correct
44	Correct	5 ms	376 KB	Output is correct
45	Correct	5 ms	376 KB	Output is correct
46	Correct	5 ms	376 KB	Output is correct
47	Correct	5 ms	376 KB	Output is correct
48	Correct	5 ms	376 KB	Output is correct
49	Correct	5 ms	376 KB	Output is correct
50	Correct	5 ms	376 KB	Output is correct
51	Correct	5 ms	376 KB	Output is correct
52	Correct	5 ms	376 KB	Output is correct
53	Correct	5 ms	504 KB	Output is correct
54	Correct	5 ms	504 KB	Output is correct
55	Correct	5 ms	376 KB	Output is correct
56	Correct	6 ms	504 KB	Output is correct
57	Correct	6 ms	504 KB	Output is correct
58	Correct	6 ms	376 KB	Output is correct
59	Correct	5 ms	376 KB	Output is correct
60	Correct	5 ms	376 KB	Output is correct
61	Correct	5 ms	504 KB	Output is correct
62	Correct	5 ms	504 KB	Output is correct
63	Correct	5 ms	376 KB	Output is correct
64	Correct	5 ms	376 KB	Output is correct
65	Correct	39 ms	4344 KB	Output is correct
66	Correct	49 ms	4964 KB	Output is correct
67	Correct	55 ms	4216 KB	Output is correct
68	Correct	60 ms	4088 KB	Output is correct
69	Correct	19 ms	3576 KB	Output is correct
70	Correct	22 ms	3576 KB	Output is correct
71	Correct	21 ms	3192 KB	Output is correct
72	Correct	21 ms	2552 KB	Output is correct
73	Correct	26 ms	3576 KB	Output is correct
74	Correct	25 ms	3192 KB	Output is correct
75	Correct	24 ms	2808 KB	Output is correct
76	Correct	24 ms	2296 KB	Output is correct
77	Correct	72 ms	14588 KB	Output is correct
78	Correct	84 ms	13176 KB	Output is correct
79	Correct	116 ms	13176 KB	Output is correct
80	Correct	116 ms	10104 KB	Output is correct
81	Correct	142 ms	10488 KB	Output is correct
82	Correct	150 ms	10232 KB	Output is correct
83	Correct	153 ms	7416 KB	Output is correct
84	Correct	128 ms	6392 KB	Output is correct
85	Correct	45 ms	7800 KB	Output is correct
86	Correct	48 ms	7752 KB	Output is correct
87	Correct	48 ms	6908 KB	Output is correct
88	Correct	48 ms	5496 KB	Output is correct
89	Correct	55 ms	7800 KB	Output is correct
90	Correct	55 ms	6948 KB	Output is correct
91	Correct	58 ms	6136 KB	Output is correct
92	Correct	53 ms	5112 KB	Output is correct

Subtask #5
37.0 / 37.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	5 ms	376 KB	Output is correct
4	Correct	6 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	376 KB	Output is correct
15	Correct	5 ms	376 KB	Output is correct
16	Correct	5 ms	376 KB	Output is correct
17	Correct	5 ms	376 KB	Output is correct
18	Correct	5 ms	376 KB	Output is correct
19	Correct	5 ms	376 KB	Output is correct
20	Correct	5 ms	376 KB	Output is correct
21	Correct	5 ms	376 KB	Output is correct
22	Correct	5 ms	376 KB	Output is correct
23	Correct	5 ms	376 KB	Output is correct
24	Correct	5 ms	380 KB	Output is correct
25	Correct	5 ms	376 KB	Output is correct
26	Correct	5 ms	376 KB	Output is correct
27	Correct	5 ms	376 KB	Output is correct
28	Correct	5 ms	380 KB	Output is correct
29	Correct	5 ms	552 KB	Output is correct
30	Correct	5 ms	376 KB	Output is correct
31	Correct	5 ms	376 KB	Output is correct
32	Correct	5 ms	376 KB	Output is correct
33	Correct	5 ms	376 KB	Output is correct
34	Correct	5 ms	376 KB	Output is correct
35	Correct	5 ms	376 KB	Output is correct
36	Correct	5 ms	376 KB	Output is correct
37	Correct	5 ms	376 KB	Output is correct
38	Correct	5 ms	376 KB	Output is correct
39	Correct	5 ms	376 KB	Output is correct
40	Correct	5 ms	376 KB	Output is correct
41	Correct	5 ms	376 KB	Output is correct
42	Correct	5 ms	376 KB	Output is correct
43	Correct	5 ms	376 KB	Output is correct
44	Correct	5 ms	376 KB	Output is correct
45	Correct	5 ms	376 KB	Output is correct
46	Correct	5 ms	376 KB	Output is correct
47	Correct	5 ms	376 KB	Output is correct
48	Correct	5 ms	376 KB	Output is correct
49	Correct	5 ms	376 KB	Output is correct
50	Correct	5 ms	376 KB	Output is correct
51	Correct	5 ms	376 KB	Output is correct
52	Correct	5 ms	376 KB	Output is correct
53	Correct	5 ms	504 KB	Output is correct
54	Correct	5 ms	504 KB	Output is correct
55	Correct	5 ms	376 KB	Output is correct
56	Correct	6 ms	504 KB	Output is correct
57	Correct	6 ms	504 KB	Output is correct
58	Correct	6 ms	376 KB	Output is correct
59	Correct	5 ms	376 KB	Output is correct
60	Correct	5 ms	376 KB	Output is correct
61	Correct	5 ms	504 KB	Output is correct
62	Correct	5 ms	504 KB	Output is correct
63	Correct	5 ms	376 KB	Output is correct
64	Correct	5 ms	376 KB	Output is correct
65	Correct	39 ms	4344 KB	Output is correct
66	Correct	49 ms	4964 KB	Output is correct
67	Correct	55 ms	4216 KB	Output is correct
68	Correct	60 ms	4088 KB	Output is correct
69	Correct	19 ms	3576 KB	Output is correct
70	Correct	22 ms	3576 KB	Output is correct
71	Correct	21 ms	3192 KB	Output is correct
72	Correct	21 ms	2552 KB	Output is correct
73	Correct	26 ms	3576 KB	Output is correct
74	Correct	25 ms	3192 KB	Output is correct
75	Correct	24 ms	2808 KB	Output is correct
76	Correct	24 ms	2296 KB	Output is correct
77	Correct	72 ms	14588 KB	Output is correct
78	Correct	84 ms	13176 KB	Output is correct
79	Correct	116 ms	13176 KB	Output is correct
80	Correct	116 ms	10104 KB	Output is correct
81	Correct	142 ms	10488 KB	Output is correct
82	Correct	150 ms	10232 KB	Output is correct
83	Correct	153 ms	7416 KB	Output is correct
84	Correct	128 ms	6392 KB	Output is correct
85	Correct	45 ms	7800 KB	Output is correct
86	Correct	48 ms	7752 KB	Output is correct
87	Correct	48 ms	6908 KB	Output is correct
88	Correct	48 ms	5496 KB	Output is correct
89	Correct	55 ms	7800 KB	Output is correct
90	Correct	55 ms	6948 KB	Output is correct
91	Correct	58 ms	6136 KB	Output is correct
92	Correct	53 ms	5112 KB	Output is correct
93	Correct	802 ms	80688 KB	Output is correct
94	Correct	646 ms	38648 KB	Output is correct
95	Correct	583 ms	30588 KB	Output is correct
96	Correct	878 ms	80504 KB	Output is correct
97	Correct	895 ms	80504 KB	Output is correct
98	Correct	796 ms	80632 KB	Output is correct
99	Correct	143 ms	33272 KB	Output is correct
100	Correct	198 ms	30840 KB	Output is correct
101	Correct	266 ms	34168 KB	Output is correct
102	Correct	317 ms	30968 KB	Output is correct
103	Correct	209 ms	14200 KB	Output is correct
104	Correct	202 ms	14200 KB	Output is correct
105	Correct	266 ms	46840 KB	Output is correct
106	Correct	446 ms	68216 KB	Output is correct
107	Correct	594 ms	28920 KB	Output is correct
108	Correct	740 ms	84604 KB	Output is correct
109	Correct	1131 ms	176152 KB	Output is correct
110	Correct	1978 ms	266744 KB	Output is correct
111	Correct	362 ms	33656 KB	Output is correct
112	Correct	334 ms	16892 KB	Output is correct
113	Correct	376 ms	20472 KB	Output is correct
114	Correct	107 ms	16888 KB	Output is correct
115	Correct	121 ms	16760 KB	Output is correct
116	Correct	132 ms	15224 KB	Output is correct
117	Correct	122 ms	11868 KB	Output is correct
118	Correct	135 ms	16760 KB	Output is correct
119	Correct	135 ms	15224 KB	Output is correct
120	Correct	128 ms	13560 KB	Output is correct
121	Correct	128 ms	11384 KB	Output is correct
122	Correct	579 ms	75636 KB	Output is correct
123	Correct	867 ms	86008 KB	Output is correct
124	Correct	908 ms	65272 KB	Output is correct
125	Correct	956 ms	58872 KB	Output is correct
126	Correct	939 ms	49528 KB	Output is correct
127	Correct	816 ms	33272 KB	Output is correct
128	Correct	685 ms	24228 KB	Output is correct
129	Correct	516 ms	16760 KB	Output is correct
130	Correct	321 ms	10108 KB	Output is correct
131	Correct	265 ms	36728 KB	Output is correct
132	Correct	309 ms	36728 KB	Output is correct
133	Correct	304 ms	33528 KB	Output is correct
134	Correct	304 ms	26360 KB	Output is correct
135	Correct	354 ms	36728 KB	Output is correct
136	Correct	326 ms	33528 KB	Output is correct
137	Correct	338 ms	30584 KB	Output is correct
138	Correct	323 ms	25592 KB	Output is correct
139	Correct	366 ms	36600 KB	Output is correct
140	Correct	370 ms	29048 KB	Output is correct
141	Correct	362 ms	23544 KB	Output is correct
142	Correct	1988 ms	167100 KB	Output is correct
143	Correct	2422 ms	145152 KB	Output is correct
144	Correct	2260 ms	92920 KB	Output is correct
145	Correct	2019 ms	73976 KB	Output is correct
146	Correct	1486 ms	51064 KB	Output is correct
147	Correct	865 ms	20280 KB	Output is correct
148	Correct	2247 ms	169860 KB	Output is correct
149	Correct	2210 ms	125556 KB	Output is correct
150	Correct	2606 ms	177528 KB	Output is correct
151	Correct	802 ms	60152 KB	Output is correct
152	Correct	800 ms	65356 KB	Output is correct
153	Correct	936 ms	80352 KB	Output is correct
154	Correct	893 ms	80248 KB	Output is correct
155	Correct	883 ms	65808 KB	Output is correct
156	Correct	916 ms	57328 KB	Output is correct
157	Correct	938 ms	74216 KB	Output is correct
158	Correct	939 ms	67832 KB	Output is correct
159	Correct	969 ms	80044 KB	Output is correct
160	Correct	985 ms	67684 KB	Output is correct
161	Correct	949 ms	53496 KB	Output is correct
162	Correct	1006 ms	78620 KB	Output is correct
163	Correct	1000 ms	73592 KB	Output is correct
164	Correct	981 ms	67736 KB	Output is correct
165	Correct	960 ms	61432 KB	Output is correct
166	Correct	928 ms	55032 KB	Output is correct
167	Correct	976 ms	47992 KB	Output is correct

답안 #208161

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 23.0 / 23.0

Subtask #4 21.0 / 21.0

Subtask #5 37.0 / 37.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
23.0 / 23.0

Subtask #4
21.0 / 21.0

Subtask #5
37.0 / 37.0