oj.uz

Submission #1011150

# Submission time Handle Problem Language Result Execution time Memory
1011150 2024-06-30T00:53:56 Z Oz121 Amusement Park (CEOI19_amusementpark) Java 11
100 / 100
 2538 ms 31664 KB 
import java.io.*;
import java.util.*;
public class amusementpark {
    public static int mod = 998244353;
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine());
        int num = Integer.parseInt(l1.nextToken()); int m = Integer.parseInt(l1.nextToken());
        
        HashMap<Integer, ArrayList<Integer>> graph = new HashMap<>();
        for (int i = 0;i<num;i++) graph.put(i,new ArrayList<>());

        for (int i = 0;i<m;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            int a = Integer.parseInt(st.nextToken())-1; int b = Integer.parseInt(st.nextToken())-1;
            graph.get(a).add(b);
        }

        //Store if a set i of vertices is independent or not
        boolean[] indep = new boolean[1<<num]; Arrays.fill(indep, true);
        for (int i = 0;i<(1<<num);i++) {
            for (int j = 0;j<num;j++) {
                if ((i&(1<<j))==0) continue;

                for (int k : graph.get(j)) {
                    if ((i&(1<<k))!=0) indep[i] = false;
                }
            }
        }

        int[] bc = new int[1<<num];
        for (int i = 0;i<(1<<num);i++) bc[i] = Integer.bitCount(i);

        //Use DP to count the number of DAGs in the given graph
        long[] dp = new long[1<<num]; //Number of DAGs in the subgraph on the set i of vertices
        dp[0] = 1;

        for (int i = 1;i<(1<<num);i++) {
            for (int j = i;j>0;j = (j-1)&i) {
                if ((i|j)!=i||!indep[j]) continue; //Ensures j is a subset of i

                int prev = i-j;
                dp[i] = (dp[i]+((bc[j]%2==0) ? -1 : 1) *dp[prev])%mod;
                dp[i] = (dp[i]+mod)%mod;
            }
        }
        
        long ans = (dp[(1<<num)-1]*m)%mod;
        ans = (ans%2==0) ? ans/2 : (ans+mod)/2;
        System.out.println(ans);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22272 KB Output is correct
2 Correct 44 ms 26376 KB Output is correct
3 Correct 49 ms 22744 KB Output is correct
4 Correct 45 ms 22364 KB Output is correct
5 Correct 45 ms 22488 KB Output is correct
6 Correct 44 ms 22356 KB Output is correct
7 Correct 46 ms 24492 KB Output is correct
8 Correct 44 ms 22256 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22272 KB Output is correct
2 Correct 44 ms 26376 KB Output is correct
3 Correct 49 ms 22744 KB Output is correct
4 Correct 45 ms 22364 KB Output is correct
5 Correct 45 ms 22488 KB Output is correct
6 Correct 44 ms 22356 KB Output is correct
7 Correct 46 ms 24492 KB Output is correct
8 Correct 44 ms 22256 KB Output is correct
9 Correct 45 ms 22148 KB Output is correct
10 Correct 45 ms 22128 KB Output is correct
11 Correct 50 ms 25956 KB Output is correct
12 Correct 47 ms 22412 KB Output is correct
13 Correct 45 ms 22196 KB Output is correct
14 Correct 45 ms 24672 KB Output is correct
15 Correct 46 ms 26820 KB Output is correct
16 Correct 46 ms 22612 KB Output is correct
17 Correct 45 ms 26552 KB Output is correct
18 Correct 46 ms 22768 KB Output is correct
19 Correct 45 ms 22572 KB Output is correct
20 Correct 48 ms 22308 KB Output is correct
21 Correct 46 ms 24228 KB Output is correct
22 Correct 45 ms 22580 KB Output is correct
23 Correct 45 ms 22416 KB Output is correct
24 Correct 45 ms 21932 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22272 KB Output is correct
2 Correct 44 ms 26376 KB Output is correct
3 Correct 49 ms 22744 KB Output is correct
4 Correct 45 ms 22364 KB Output is correct
5 Correct 45 ms 22488 KB Output is correct
6 Correct 44 ms 22356 KB Output is correct
7 Correct 46 ms 24492 KB Output is correct
8 Correct 44 ms 22256 KB Output is correct
9 Correct 45 ms 22148 KB Output is correct
10 Correct 45 ms 22128 KB Output is correct
11 Correct 50 ms 25956 KB Output is correct
12 Correct 47 ms 22412 KB Output is correct
13 Correct 45 ms 22196 KB Output is correct
14 Correct 45 ms 24672 KB Output is correct
15 Correct 46 ms 26820 KB Output is correct
16 Correct 46 ms 22612 KB Output is correct
17 Correct 45 ms 26552 KB Output is correct
18 Correct 46 ms 22768 KB Output is correct
19 Correct 45 ms 22572 KB Output is correct
20 Correct 48 ms 22308 KB Output is correct
21 Correct 46 ms 24228 KB Output is correct
22 Correct 45 ms 22580 KB Output is correct
23 Correct 45 ms 22416 KB Output is correct
24 Correct 45 ms 21932 KB Output is correct
25 Correct 52 ms 22340 KB Output is correct
26 Correct 50 ms 22604 KB Output is correct
27 Correct 49 ms 21920 KB Output is correct
28 Correct 58 ms 22276 KB Output is correct
29 Correct 48 ms 22416 KB Output is correct
30 Correct 42 ms 22392 KB Output is correct
31 Correct 46 ms 24772 KB Output is correct
32 Correct 45 ms 22176 KB Output is correct
33 Correct 50 ms 24680 KB Output is correct
34 Correct 51 ms 24552 KB Output is correct
35 Correct 49 ms 24344 KB Output is correct
36 Correct 48 ms 22344 KB Output is correct
37 Correct 49 ms 24116 KB Output is correct
38 Correct 47 ms 22524 KB Output is correct
39 Correct 51 ms 22652 KB Output is correct
40 Correct 54 ms 24584 KB Output is correct
41 Correct 57 ms 22380 KB Output is correct
42 Correct 54 ms 22452 KB Output is correct
43 Correct 55 ms 22616 KB Output is correct
44 Correct 61 ms 22740 KB Output is correct
45 Correct 61 ms 22740 KB Output is correct
46 Correct 59 ms 24824 KB Output is correct
47 Correct 59 ms 22632 KB Output is correct
48 Correct 59 ms 22688 KB Output is correct
49 Correct 55 ms 26592 KB Output is correct
50 Correct 57 ms 22908 KB Output is correct
51 Correct 57 ms 22380 KB Output is correct
52 Correct 60 ms 26596 KB Output is correct
53 Correct 59 ms 24468 KB Output is correct
54 Correct 59 ms 22744 KB Output is correct
55 Correct 63 ms 22424 KB Output is correct
56 Correct 70 ms 23204 KB Output is correct
57 Correct 69 ms 27336 KB Output is correct
58 Correct 70 ms 23052 KB Output is correct
59 Correct 76 ms 27432 KB Output is correct
60 Correct 79 ms 23188 KB Output is correct
61 Correct 63 ms 22396 KB Output is correct
62 Correct 59 ms 22568 KB Output is correct
63 Correct 61 ms 22676 KB Output is correct
64 Correct 64 ms 24660 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22272 KB Output is correct
2 Correct 44 ms 26376 KB Output is correct
3 Correct 49 ms 22744 KB Output is correct
4 Correct 45 ms 22364 KB Output is correct
5 Correct 45 ms 22488 KB Output is correct
6 Correct 44 ms 22356 KB Output is correct
7 Correct 46 ms 24492 KB Output is correct
8 Correct 44 ms 22256 KB Output is correct
9 Correct 45 ms 22148 KB Output is correct
10 Correct 45 ms 22128 KB Output is correct
11 Correct 50 ms 25956 KB Output is correct
12 Correct 47 ms 22412 KB Output is correct
13 Correct 45 ms 22196 KB Output is correct
14 Correct 45 ms 24672 KB Output is correct
15 Correct 46 ms 26820 KB Output is correct
16 Correct 46 ms 22612 KB Output is correct
17 Correct 45 ms 26552 KB Output is correct
18 Correct 46 ms 22768 KB Output is correct
19 Correct 45 ms 22572 KB Output is correct
20 Correct 48 ms 22308 KB Output is correct
21 Correct 46 ms 24228 KB Output is correct
22 Correct 45 ms 22580 KB Output is correct
23 Correct 45 ms 22416 KB Output is correct
24 Correct 45 ms 21932 KB Output is correct
25 Correct 52 ms 22340 KB Output is correct
26 Correct 50 ms 22604 KB Output is correct
27 Correct 49 ms 21920 KB Output is correct
28 Correct 58 ms 22276 KB Output is correct
29 Correct 48 ms 22416 KB Output is correct
30 Correct 42 ms 22392 KB Output is correct
31 Correct 46 ms 24772 KB Output is correct
32 Correct 45 ms 22176 KB Output is correct
33 Correct 50 ms 24680 KB Output is correct
34 Correct 51 ms 24552 KB Output is correct
35 Correct 49 ms 24344 KB Output is correct
36 Correct 48 ms 22344 KB Output is correct
37 Correct 49 ms 24116 KB Output is correct
38 Correct 47 ms 22524 KB Output is correct
39 Correct 51 ms 22652 KB Output is correct
40 Correct 54 ms 24584 KB Output is correct
41 Correct 57 ms 22380 KB Output is correct
42 Correct 54 ms 22452 KB Output is correct
43 Correct 55 ms 22616 KB Output is correct
44 Correct 61 ms 22740 KB Output is correct
45 Correct 61 ms 22740 KB Output is correct
46 Correct 59 ms 24824 KB Output is correct
47 Correct 59 ms 22632 KB Output is correct
48 Correct 59 ms 22688 KB Output is correct
49 Correct 55 ms 26592 KB Output is correct
50 Correct 57 ms 22908 KB Output is correct
51 Correct 57 ms 22380 KB Output is correct
52 Correct 60 ms 26596 KB Output is correct
53 Correct 59 ms 24468 KB Output is correct
54 Correct 59 ms 22744 KB Output is correct
55 Correct 63 ms 22424 KB Output is correct
56 Correct 70 ms 23204 KB Output is correct
57 Correct 69 ms 27336 KB Output is correct
58 Correct 70 ms 23052 KB Output is correct
59 Correct 76 ms 27432 KB Output is correct
60 Correct 79 ms 23188 KB Output is correct
61 Correct 63 ms 22396 KB Output is correct
62 Correct 59 ms 22568 KB Output is correct
63 Correct 61 ms 22676 KB Output is correct
64 Correct 64 ms 24660 KB Output is correct
65 Correct 96 ms 28060 KB Output is correct
66 Correct 95 ms 25012 KB Output is correct
67 Correct 95 ms 26880 KB Output is correct
68 Correct 94 ms 28284 KB Output is correct
69 Correct 105 ms 24088 KB Output is correct
70 Correct 99 ms 25916 KB Output is correct
71 Correct 98 ms 25908 KB Output is correct
72 Correct 121 ms 23676 KB Output is correct
73 Correct 96 ms 25152 KB Output is correct
74 Correct 99 ms 23584 KB Output is correct
75 Correct 86 ms 24212 KB Output is correct
76 Correct 102 ms 23744 KB Output is correct
77 Correct 98 ms 23984 KB Output is correct
78 Correct 100 ms 23660 KB Output is correct
79 Correct 110 ms 24572 KB Output is correct
80 Correct 102 ms 23748 KB Output is correct
81 Correct 114 ms 24600 KB Output is correct
82 Correct 116 ms 24308 KB Output is correct
83 Correct 106 ms 26416 KB Output is correct
84 Correct 114 ms 24584 KB Output is correct
85 Correct 130 ms 23892 KB Output is correct
86 Correct 130 ms 23436 KB Output is correct
87 Correct 116 ms 23816 KB Output is correct
88 Correct 130 ms 24360 KB Output is correct
89 Correct 117 ms 25128 KB Output is correct
90 Correct 105 ms 24036 KB Output is correct
91 Correct 112 ms 24124 KB Output is correct
92 Correct 125 ms 24064 KB Output is correct

Subtask #5
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 22272 KB Output is correct
2 Correct 44 ms 26376 KB Output is correct
3 Correct 49 ms 22744 KB Output is correct
4 Correct 45 ms 22364 KB Output is correct
5 Correct 45 ms 22488 KB Output is correct
6 Correct 44 ms 22356 KB Output is correct
7 Correct 46 ms 24492 KB Output is correct
8 Correct 44 ms 22256 KB Output is correct
9 Correct 45 ms 22148 KB Output is correct
10 Correct 45 ms 22128 KB Output is correct
11 Correct 50 ms 25956 KB Output is correct
12 Correct 47 ms 22412 KB Output is correct
13 Correct 45 ms 22196 KB Output is correct
14 Correct 45 ms 24672 KB Output is correct
15 Correct 46 ms 26820 KB Output is correct
16 Correct 46 ms 22612 KB Output is correct
17 Correct 45 ms 26552 KB Output is correct
18 Correct 46 ms 22768 KB Output is correct
19 Correct 45 ms 22572 KB Output is correct
20 Correct 48 ms 22308 KB Output is correct
21 Correct 46 ms 24228 KB Output is correct
22 Correct 45 ms 22580 KB Output is correct
23 Correct 45 ms 22416 KB Output is correct
24 Correct 45 ms 21932 KB Output is correct
25 Correct 52 ms 22340 KB Output is correct
26 Correct 50 ms 22604 KB Output is correct
27 Correct 49 ms 21920 KB Output is correct
28 Correct 58 ms 22276 KB Output is correct
29 Correct 48 ms 22416 KB Output is correct
30 Correct 42 ms 22392 KB Output is correct
31 Correct 46 ms 24772 KB Output is correct
32 Correct 45 ms 22176 KB Output is correct
33 Correct 50 ms 24680 KB Output is correct
34 Correct 51 ms 24552 KB Output is correct
35 Correct 49 ms 24344 KB Output is correct
36 Correct 48 ms 22344 KB Output is correct
37 Correct 49 ms 24116 KB Output is correct
38 Correct 47 ms 22524 KB Output is correct
39 Correct 51 ms 22652 KB Output is correct
40 Correct 54 ms 24584 KB Output is correct
41 Correct 57 ms 22380 KB Output is correct
42 Correct 54 ms 22452 KB Output is correct
43 Correct 55 ms 22616 KB Output is correct
44 Correct 61 ms 22740 KB Output is correct
45 Correct 61 ms 22740 KB Output is correct
46 Correct 59 ms 24824 KB Output is correct
47 Correct 59 ms 22632 KB Output is correct
48 Correct 59 ms 22688 KB Output is correct
49 Correct 55 ms 26592 KB Output is correct
50 Correct 57 ms 22908 KB Output is correct
51 Correct 57 ms 22380 KB Output is correct
52 Correct 60 ms 26596 KB Output is correct
53 Correct 59 ms 24468 KB Output is correct
54 Correct 59 ms 22744 KB Output is correct
55 Correct 63 ms 22424 KB Output is correct
56 Correct 70 ms 23204 KB Output is correct
57 Correct 69 ms 27336 KB Output is correct
58 Correct 70 ms 23052 KB Output is correct
59 Correct 76 ms 27432 KB Output is correct
60 Correct 79 ms 23188 KB Output is correct
61 Correct 63 ms 22396 KB Output is correct
62 Correct 59 ms 22568 KB Output is correct
63 Correct 61 ms 22676 KB Output is correct
64 Correct 64 ms 24660 KB Output is correct
65 Correct 96 ms 28060 KB Output is correct
66 Correct 95 ms 25012 KB Output is correct
67 Correct 95 ms 26880 KB Output is correct
68 Correct 94 ms 28284 KB Output is correct
69 Correct 105 ms 24088 KB Output is correct
70 Correct 99 ms 25916 KB Output is correct
71 Correct 98 ms 25908 KB Output is correct
72 Correct 121 ms 23676 KB Output is correct
73 Correct 96 ms 25152 KB Output is correct
74 Correct 99 ms 23584 KB Output is correct
75 Correct 86 ms 24212 KB Output is correct
76 Correct 102 ms 23744 KB Output is correct
77 Correct 98 ms 23984 KB Output is correct
78 Correct 100 ms 23660 KB Output is correct
79 Correct 110 ms 24572 KB Output is correct
80 Correct 102 ms 23748 KB Output is correct
81 Correct 114 ms 24600 KB Output is correct
82 Correct 116 ms 24308 KB Output is correct
83 Correct 106 ms 26416 KB Output is correct
84 Correct 114 ms 24584 KB Output is correct
85 Correct 130 ms 23892 KB Output is correct
86 Correct 130 ms 23436 KB Output is correct
87 Correct 116 ms 23816 KB Output is correct
88 Correct 130 ms 24360 KB Output is correct
89 Correct 117 ms 25128 KB Output is correct
90 Correct 105 ms 24036 KB Output is correct
91 Correct 112 ms 24124 KB Output is correct
92 Correct 125 ms 24064 KB Output is correct
93 Correct 1315 ms 27132 KB Output is correct
94 Correct 1333 ms 27668 KB Output is correct
95 Correct 1324 ms 26932 KB Output is correct
96 Correct 1046 ms 28420 KB Output is correct
97 Correct 960 ms 27240 KB Output is correct
98 Correct 1060 ms 31664 KB Output is correct
99 Correct 168 ms 23664 KB Output is correct
100 Correct 161 ms 23868 KB Output is correct
101 Correct 150 ms 23832 KB Output is correct
102 Correct 153 ms 25972 KB Output is correct
103 Correct 892 ms 25968 KB Output is correct
104 Correct 527 ms 24948 KB Output is correct
105 Correct 410 ms 26396 KB Output is correct
106 Correct 319 ms 25280 KB Output is correct
107 Correct 2538 ms 26500 KB Output is correct
108 Correct 1004 ms 27452 KB Output is correct
109 Correct 743 ms 27320 KB Output is correct
110 Correct 673 ms 27516 KB Output is correct
111 Correct 144 ms 24816 KB Output is correct
112 Correct 146 ms 24884 KB Output is correct
113 Correct 147 ms 27208 KB Output is correct
114 Correct 259 ms 23772 KB Output is correct
115 Correct 213 ms 23524 KB Output is correct
116 Correct 225 ms 24032 KB Output is correct
117 Correct 244 ms 24140 KB Output is correct
118 Correct 191 ms 24752 KB Output is correct
119 Correct 193 ms 23352 KB Output is correct
120 Correct 200 ms 23872 KB Output is correct
121 Correct 208 ms 23804 KB Output is correct
122 Correct 281 ms 28748 KB Output is correct
123 Correct 274 ms 24228 KB Output is correct
124 Correct 296 ms 24568 KB Output is correct
125 Correct 270 ms 27000 KB Output is correct
126 Correct 283 ms 24660 KB Output is correct
127 Correct 288 ms 24724 KB Output is correct
128 Correct 270 ms 24668 KB Output is correct
129 Correct 262 ms 24408 KB Output is correct
130 Correct 259 ms 24764 KB Output is correct
131 Correct 677 ms 24544 KB Output is correct
132 Correct 517 ms 26704 KB Output is correct
133 Correct 531 ms 24896 KB Output is correct
134 Correct 550 ms 24800 KB Output is correct
135 Correct 408 ms 24560 KB Output is correct
136 Correct 444 ms 24528 KB Output is correct
137 Correct 428 ms 26764 KB Output is correct
138 Correct 445 ms 24548 KB Output is correct
139 Correct 365 ms 26972 KB Output is correct
140 Correct 363 ms 24344 KB Output is correct
141 Correct 374 ms 27080 KB Output is correct
142 Correct 635 ms 25508 KB Output is correct
143 Correct 695 ms 27416 KB Output is correct
144 Correct 645 ms 27048 KB Output is correct
145 Correct 621 ms 27152 KB Output is correct
146 Correct 558 ms 27392 KB Output is correct
147 Correct 506 ms 29648 KB Output is correct
148 Correct 659 ms 27144 KB Output is correct
149 Correct 588 ms 27528 KB Output is correct
150 Correct 626 ms 27532 KB Output is correct
151 Correct 757 ms 29360 KB Output is correct
152 Correct 737 ms 27528 KB Output is correct
153 Correct 1056 ms 27164 KB Output is correct
154 Correct 1072 ms 27268 KB Output is correct
155 Correct 1171 ms 27112 KB Output is correct
156 Correct 1171 ms 27608 KB Output is correct
157 Correct 1020 ms 28996 KB Output is correct
158 Correct 1089 ms 27956 KB Output is correct
159 Correct 948 ms 27240 KB Output is correct
160 Correct 869 ms 27312 KB Output is correct
161 Correct 934 ms 27352 KB Output is correct
162 Correct 781 ms 27684 KB Output is correct
163 Correct 769 ms 27444 KB Output is correct
164 Correct 767 ms 27228 KB Output is correct
165 Correct 784 ms 27120 KB Output is correct
166 Correct 781 ms 27184 KB Output is correct
167 Correct 783 ms 27668 KB Output is correct