# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

313775 | 2020-10-17T04:26:18 Z | jhnah917 | Amusement Park (CEOI19_amusementpark) | C++14 | 3000 ms | 165380 KB |

#include <bits/stdc++.h> #define x first #define y second #define all(v) v.begin(), v.end() #define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end()) using namespace std; typedef long long ll; typedef pair<int, int> p; const int pw_2_15 = 32768; const int pw_3_18 = 387420489; const int mod = 998244353; int pw[22]; int n, m, bit[22]; vector<int> g[22]; map<p, ll> dp; bool in(int Set, int Elem){ return (Set & (1 << Elem)) != 0; } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); pw[0] = 1; for(int i=1; i<22; i++) pw[i] = pw[i-1] * 3; cin >> n >> m; for(int i=0; i<m; i++){ int s, e; cin >> s >> e; s--; e--; g[s].push_back(e); g[e].push_back(s); bit[s] |= (1 << e); bit[e] |= (1 << s); } dp[p(0, 0)] = 1; for(auto i : dp){ int a = i.x.x, b = i.x.y; ll cnt = i.y; for(int j=0; j<n; j++) if(!in(a|b, j)) { int a_ = (a | (1 << j)); int b_ = ((b | ((1<<j)-1)) & ~bit[j] & ~a); dp[p(a_, b_)] = (cnt + dp[p(a_, b_)]) % mod; } } ll res = dp[p((1<<n)-1, 0)]; res = res * m % mod * (mod/2+1) % mod; cout << res; }

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 384 KB | Output is correct |

4 | Correct | 1 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 1 ms | 384 KB | Output is correct |

7 | Correct | 1 ms | 288 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 384 KB | Output is correct |

4 | Correct | 1 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 1 ms | 384 KB | Output is correct |

7 | Correct | 1 ms | 288 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

9 | Correct | 1 ms | 384 KB | Output is correct |

10 | Correct | 1 ms | 384 KB | Output is correct |

11 | Correct | 1 ms | 384 KB | Output is correct |

12 | Correct | 1 ms | 384 KB | Output is correct |

13 | Correct | 0 ms | 384 KB | Output is correct |

14 | Correct | 0 ms | 384 KB | Output is correct |

15 | Correct | 0 ms | 384 KB | Output is correct |

16 | Correct | 1 ms | 384 KB | Output is correct |

17 | Correct | 1 ms | 384 KB | Output is correct |

18 | Correct | 0 ms | 384 KB | Output is correct |

19 | Correct | 1 ms | 384 KB | Output is correct |

20 | Correct | 0 ms | 384 KB | Output is correct |

21 | Correct | 1 ms | 384 KB | Output is correct |

22 | Correct | 0 ms | 384 KB | Output is correct |

23 | Correct | 1 ms | 384 KB | Output is correct |

24 | Correct | 1 ms | 384 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 384 KB | Output is correct |

4 | Correct | 1 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 1 ms | 384 KB | Output is correct |

7 | Correct | 1 ms | 288 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

9 | Correct | 1 ms | 384 KB | Output is correct |

10 | Correct | 1 ms | 384 KB | Output is correct |

11 | Correct | 1 ms | 384 KB | Output is correct |

12 | Correct | 1 ms | 384 KB | Output is correct |

13 | Correct | 0 ms | 384 KB | Output is correct |

14 | Correct | 0 ms | 384 KB | Output is correct |

15 | Correct | 0 ms | 384 KB | Output is correct |

16 | Correct | 1 ms | 384 KB | Output is correct |

17 | Correct | 1 ms | 384 KB | Output is correct |

18 | Correct | 0 ms | 384 KB | Output is correct |

19 | Correct | 1 ms | 384 KB | Output is correct |

20 | Correct | 0 ms | 384 KB | Output is correct |

21 | Correct | 1 ms | 384 KB | Output is correct |

22 | Correct | 0 ms | 384 KB | Output is correct |

23 | Correct | 1 ms | 384 KB | Output is correct |

24 | Correct | 1 ms | 384 KB | Output is correct |

25 | Correct | 1 ms | 384 KB | Output is correct |

26 | Correct | 1 ms | 384 KB | Output is correct |

27 | Correct | 1 ms | 384 KB | Output is correct |

28 | Correct | 1 ms | 384 KB | Output is correct |

29 | Correct | 1 ms | 384 KB | Output is correct |

30 | Correct | 1 ms | 384 KB | Output is correct |

31 | Correct | 1 ms | 384 KB | Output is correct |

32 | Correct | 1 ms | 384 KB | Output is correct |

33 | Correct | 1 ms | 384 KB | Output is correct |

34 | Correct | 1 ms | 384 KB | Output is correct |

35 | Correct | 1 ms | 384 KB | Output is correct |

36 | Correct | 1 ms | 384 KB | Output is correct |

37 | Correct | 1 ms | 384 KB | Output is correct |

38 | Correct | 1 ms | 384 KB | Output is correct |

39 | Correct | 1 ms | 384 KB | Output is correct |

40 | Correct | 1 ms | 384 KB | Output is correct |

41 | Correct | 1 ms | 384 KB | Output is correct |

42 | Correct | 1 ms | 384 KB | Output is correct |

43 | Correct | 2 ms | 384 KB | Output is correct |

44 | Correct | 1 ms | 384 KB | Output is correct |

45 | Correct | 2 ms | 384 KB | Output is correct |

46 | Correct | 1 ms | 384 KB | Output is correct |

47 | Correct | 1 ms | 384 KB | Output is correct |

48 | Correct | 1 ms | 384 KB | Output is correct |

49 | Correct | 1 ms | 384 KB | Output is correct |

50 | Correct | 1 ms | 384 KB | Output is correct |

51 | Correct | 1 ms | 384 KB | Output is correct |

52 | Correct | 1 ms | 384 KB | Output is correct |

53 | Correct | 1 ms | 512 KB | Output is correct |

54 | Correct | 2 ms | 512 KB | Output is correct |

55 | Correct | 2 ms | 512 KB | Output is correct |

56 | Correct | 3 ms | 640 KB | Output is correct |

57 | Correct | 3 ms | 512 KB | Output is correct |

58 | Correct | 2 ms | 512 KB | Output is correct |

59 | Correct | 2 ms | 512 KB | Output is correct |

60 | Correct | 1 ms | 384 KB | Output is correct |

61 | Correct | 1 ms | 512 KB | Output is correct |

62 | Correct | 2 ms | 512 KB | Output is correct |

63 | Correct | 2 ms | 512 KB | Output is correct |

64 | Correct | 2 ms | 512 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 384 KB | Output is correct |

4 | Correct | 1 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 1 ms | 384 KB | Output is correct |

7 | Correct | 1 ms | 288 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

9 | Correct | 1 ms | 384 KB | Output is correct |

10 | Correct | 1 ms | 384 KB | Output is correct |

11 | Correct | 1 ms | 384 KB | Output is correct |

12 | Correct | 1 ms | 384 KB | Output is correct |

13 | Correct | 0 ms | 384 KB | Output is correct |

14 | Correct | 0 ms | 384 KB | Output is correct |

15 | Correct | 0 ms | 384 KB | Output is correct |

16 | Correct | 1 ms | 384 KB | Output is correct |

17 | Correct | 1 ms | 384 KB | Output is correct |

18 | Correct | 0 ms | 384 KB | Output is correct |

19 | Correct | 1 ms | 384 KB | Output is correct |

20 | Correct | 0 ms | 384 KB | Output is correct |

21 | Correct | 1 ms | 384 KB | Output is correct |

22 | Correct | 0 ms | 384 KB | Output is correct |

23 | Correct | 1 ms | 384 KB | Output is correct |

24 | Correct | 1 ms | 384 KB | Output is correct |

25 | Correct | 1 ms | 384 KB | Output is correct |

26 | Correct | 1 ms | 384 KB | Output is correct |

27 | Correct | 1 ms | 384 KB | Output is correct |

28 | Correct | 1 ms | 384 KB | Output is correct |

29 | Correct | 1 ms | 384 KB | Output is correct |

30 | Correct | 1 ms | 384 KB | Output is correct |

31 | Correct | 1 ms | 384 KB | Output is correct |

32 | Correct | 1 ms | 384 KB | Output is correct |

33 | Correct | 1 ms | 384 KB | Output is correct |

34 | Correct | 1 ms | 384 KB | Output is correct |

35 | Correct | 1 ms | 384 KB | Output is correct |

36 | Correct | 1 ms | 384 KB | Output is correct |

37 | Correct | 1 ms | 384 KB | Output is correct |

38 | Correct | 1 ms | 384 KB | Output is correct |

39 | Correct | 1 ms | 384 KB | Output is correct |

40 | Correct | 1 ms | 384 KB | Output is correct |

41 | Correct | 1 ms | 384 KB | Output is correct |

42 | Correct | 1 ms | 384 KB | Output is correct |

43 | Correct | 2 ms | 384 KB | Output is correct |

44 | Correct | 1 ms | 384 KB | Output is correct |

45 | Correct | 2 ms | 384 KB | Output is correct |

46 | Correct | 1 ms | 384 KB | Output is correct |

47 | Correct | 1 ms | 384 KB | Output is correct |

48 | Correct | 1 ms | 384 KB | Output is correct |

49 | Correct | 1 ms | 384 KB | Output is correct |

50 | Correct | 1 ms | 384 KB | Output is correct |

51 | Correct | 1 ms | 384 KB | Output is correct |

52 | Correct | 1 ms | 384 KB | Output is correct |

53 | Correct | 1 ms | 512 KB | Output is correct |

54 | Correct | 2 ms | 512 KB | Output is correct |

55 | Correct | 2 ms | 512 KB | Output is correct |

56 | Correct | 3 ms | 640 KB | Output is correct |

57 | Correct | 3 ms | 512 KB | Output is correct |

58 | Correct | 2 ms | 512 KB | Output is correct |

59 | Correct | 2 ms | 512 KB | Output is correct |

60 | Correct | 1 ms | 384 KB | Output is correct |

61 | Correct | 1 ms | 512 KB | Output is correct |

62 | Correct | 2 ms | 512 KB | Output is correct |

63 | Correct | 2 ms | 512 KB | Output is correct |

64 | Correct | 2 ms | 512 KB | Output is correct |

65 | Correct | 85 ms | 6648 KB | Output is correct |

66 | Correct | 125 ms | 8668 KB | Output is correct |

67 | Correct | 111 ms | 7928 KB | Output is correct |

68 | Correct | 115 ms | 7416 KB | Output is correct |

69 | Correct | 28 ms | 2936 KB | Output is correct |

70 | Correct | 39 ms | 3576 KB | Output is correct |

71 | Correct | 41 ms | 3448 KB | Output is correct |

72 | Correct | 41 ms | 3512 KB | Output is correct |

73 | Correct | 39 ms | 3576 KB | Output is correct |

74 | Correct | 42 ms | 3576 KB | Output is correct |

75 | Correct | 50 ms | 3568 KB | Output is correct |

76 | Correct | 43 ms | 3576 KB | Output is correct |

77 | Correct | 186 ms | 15324 KB | Output is correct |

78 | Correct | 220 ms | 17016 KB | Output is correct |

79 | Correct | 325 ms | 21092 KB | Output is correct |

80 | Correct | 286 ms | 17528 KB | Output is correct |

81 | Correct | 328 ms | 19320 KB | Output is correct |

82 | Correct | 287 ms | 17420 KB | Output is correct |

83 | Correct | 309 ms | 16748 KB | Output is correct |

84 | Correct | 204 ms | 12024 KB | Output is correct |

85 | Correct | 67 ms | 5752 KB | Output is correct |

86 | Correct | 90 ms | 7032 KB | Output is correct |

87 | Correct | 90 ms | 7032 KB | Output is correct |

88 | Correct | 101 ms | 7032 KB | Output is correct |

89 | Correct | 99 ms | 7260 KB | Output is correct |

90 | Correct | 103 ms | 7380 KB | Output is correct |

91 | Correct | 100 ms | 7288 KB | Output is correct |

92 | Correct | 102 ms | 7288 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 0 ms | 256 KB | Output is correct |

2 | Correct | 1 ms | 384 KB | Output is correct |

3 | Correct | 1 ms | 384 KB | Output is correct |

4 | Correct | 1 ms | 384 KB | Output is correct |

5 | Correct | 1 ms | 384 KB | Output is correct |

6 | Correct | 1 ms | 384 KB | Output is correct |

7 | Correct | 1 ms | 288 KB | Output is correct |

8 | Correct | 1 ms | 384 KB | Output is correct |

9 | Correct | 1 ms | 384 KB | Output is correct |

10 | Correct | 1 ms | 384 KB | Output is correct |

11 | Correct | 1 ms | 384 KB | Output is correct |

12 | Correct | 1 ms | 384 KB | Output is correct |

13 | Correct | 0 ms | 384 KB | Output is correct |

14 | Correct | 0 ms | 384 KB | Output is correct |

15 | Correct | 0 ms | 384 KB | Output is correct |

16 | Correct | 1 ms | 384 KB | Output is correct |

17 | Correct | 1 ms | 384 KB | Output is correct |

18 | Correct | 0 ms | 384 KB | Output is correct |

19 | Correct | 1 ms | 384 KB | Output is correct |

20 | Correct | 0 ms | 384 KB | Output is correct |

21 | Correct | 1 ms | 384 KB | Output is correct |

22 | Correct | 0 ms | 384 KB | Output is correct |

23 | Correct | 1 ms | 384 KB | Output is correct |

24 | Correct | 1 ms | 384 KB | Output is correct |

25 | Correct | 1 ms | 384 KB | Output is correct |

26 | Correct | 1 ms | 384 KB | Output is correct |

27 | Correct | 1 ms | 384 KB | Output is correct |

28 | Correct | 1 ms | 384 KB | Output is correct |

29 | Correct | 1 ms | 384 KB | Output is correct |

30 | Correct | 1 ms | 384 KB | Output is correct |

31 | Correct | 1 ms | 384 KB | Output is correct |

32 | Correct | 1 ms | 384 KB | Output is correct |

33 | Correct | 1 ms | 384 KB | Output is correct |

34 | Correct | 1 ms | 384 KB | Output is correct |

35 | Correct | 1 ms | 384 KB | Output is correct |

36 | Correct | 1 ms | 384 KB | Output is correct |

37 | Correct | 1 ms | 384 KB | Output is correct |

38 | Correct | 1 ms | 384 KB | Output is correct |

39 | Correct | 1 ms | 384 KB | Output is correct |

40 | Correct | 1 ms | 384 KB | Output is correct |

41 | Correct | 1 ms | 384 KB | Output is correct |

42 | Correct | 1 ms | 384 KB | Output is correct |

43 | Correct | 2 ms | 384 KB | Output is correct |

44 | Correct | 1 ms | 384 KB | Output is correct |

45 | Correct | 2 ms | 384 KB | Output is correct |

46 | Correct | 1 ms | 384 KB | Output is correct |

47 | Correct | 1 ms | 384 KB | Output is correct |

48 | Correct | 1 ms | 384 KB | Output is correct |

49 | Correct | 1 ms | 384 KB | Output is correct |

50 | Correct | 1 ms | 384 KB | Output is correct |

51 | Correct | 1 ms | 384 KB | Output is correct |

52 | Correct | 1 ms | 384 KB | Output is correct |

53 | Correct | 1 ms | 512 KB | Output is correct |

54 | Correct | 2 ms | 512 KB | Output is correct |

55 | Correct | 2 ms | 512 KB | Output is correct |

56 | Correct | 3 ms | 640 KB | Output is correct |

57 | Correct | 3 ms | 512 KB | Output is correct |

58 | Correct | 2 ms | 512 KB | Output is correct |

59 | Correct | 2 ms | 512 KB | Output is correct |

60 | Correct | 1 ms | 384 KB | Output is correct |

61 | Correct | 1 ms | 512 KB | Output is correct |

62 | Correct | 2 ms | 512 KB | Output is correct |

63 | Correct | 2 ms | 512 KB | Output is correct |

64 | Correct | 2 ms | 512 KB | Output is correct |

65 | Correct | 85 ms | 6648 KB | Output is correct |

66 | Correct | 125 ms | 8668 KB | Output is correct |

67 | Correct | 111 ms | 7928 KB | Output is correct |

68 | Correct | 115 ms | 7416 KB | Output is correct |

69 | Correct | 28 ms | 2936 KB | Output is correct |

70 | Correct | 39 ms | 3576 KB | Output is correct |

71 | Correct | 41 ms | 3448 KB | Output is correct |

72 | Correct | 41 ms | 3512 KB | Output is correct |

73 | Correct | 39 ms | 3576 KB | Output is correct |

74 | Correct | 42 ms | 3576 KB | Output is correct |

75 | Correct | 50 ms | 3568 KB | Output is correct |

76 | Correct | 43 ms | 3576 KB | Output is correct |

77 | Correct | 186 ms | 15324 KB | Output is correct |

78 | Correct | 220 ms | 17016 KB | Output is correct |

79 | Correct | 325 ms | 21092 KB | Output is correct |

80 | Correct | 286 ms | 17528 KB | Output is correct |

81 | Correct | 328 ms | 19320 KB | Output is correct |

82 | Correct | 287 ms | 17420 KB | Output is correct |

83 | Correct | 309 ms | 16748 KB | Output is correct |

84 | Correct | 204 ms | 12024 KB | Output is correct |

85 | Correct | 67 ms | 5752 KB | Output is correct |

86 | Correct | 90 ms | 7032 KB | Output is correct |

87 | Correct | 90 ms | 7032 KB | Output is correct |

88 | Correct | 101 ms | 7032 KB | Output is correct |

89 | Correct | 99 ms | 7260 KB | Output is correct |

90 | Correct | 103 ms | 7380 KB | Output is correct |

91 | Correct | 100 ms | 7288 KB | Output is correct |

92 | Correct | 102 ms | 7288 KB | Output is correct |

93 | Correct | 1303 ms | 62968 KB | Output is correct |

94 | Correct | 443 ms | 26748 KB | Output is correct |

95 | Correct | 189 ms | 18936 KB | Output is correct |

96 | Correct | 1375 ms | 67064 KB | Output is correct |

97 | Correct | 1151 ms | 66116 KB | Output is correct |

98 | Correct | 1082 ms | 61928 KB | Output is correct |

99 | Correct | 269 ms | 22776 KB | Output is correct |

100 | Correct | 518 ms | 35448 KB | Output is correct |

101 | Correct | 728 ms | 46072 KB | Output is correct |

102 | Correct | 813 ms | 48500 KB | Output is correct |

103 | Correct | 58 ms | 8568 KB | Output is correct |

104 | Correct | 81 ms | 9208 KB | Output is correct |

105 | Correct | 275 ms | 24760 KB | Output is correct |

106 | Correct | 1100 ms | 72184 KB | Output is correct |

107 | Correct | 126 ms | 16760 KB | Output is correct |

108 | Correct | 668 ms | 56532 KB | Output is correct |

109 | Correct | 2615 ms | 158292 KB | Output is correct |

110 | Execution timed out | 3081 ms | 165380 KB | Time limit exceeded |

111 | Halted | 0 ms | 0 KB | - |