Submission #1011150

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011150		Oz121	Amusement Park (CEOI19_amusementpark)	Java	100 / 100	2538 ms	31664 KiB

amusementpark

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 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37