Submission #1066674

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1066674	2024-08-20T04:44:58 Z	vjudge1	Amusement Park (CEOI19_amusementpark)	C++17	42 / 100	11 ms	604 KB

amusementpark

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bitset<1<<18>indep;
ll dp[1<<18];
const int mod=1e9+7;
int EDG[20][20];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        EDG[a][b]=1;
    }
    for(int i=1;i<1<<n;i++){
        vector<int>v;
        for(int j=0;j<n;j++)
            if(i&1<<j)
                v.push_back(j+1);
        int bad=0;
        for(auto i:v)
            for(auto j:v)
                if(EDG[i][j])
                    bad=1;
        indep[i]=!bad;
    }
    dp[0]=1;
    for(int i=1;i<1<<n;i++)
        for(int j=i;j;j=j-1&i){
            if(!indep[j])continue;
            int cnt=__builtin_popcount(j);
            dp[i]=(dp[i]+dp[i^j]*(cnt&1?1:-1))%mod;
        }
    cout<<dp[(1<<n)-1]*m%mod*(ll)(5e8+4)%mod<<'\n';
}

Compilation message

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:30:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |         for(int j=i;j;j=j-1&i){
      |                         ~^~

Subtask #1
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	448 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	448 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct

Subtask #3
23.0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	448 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	1 ms	452 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	1 ms	604 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	1 ms	600 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	1 ms	348 KB	Output is correct
42	Correct	1 ms	344 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	1 ms	600 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	1 ms	348 KB	Output is correct
48	Correct	0 ms	348 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	0 ms	348 KB	Output is correct
52	Correct	1 ms	344 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Correct	1 ms	348 KB	Output is correct
55	Correct	1 ms	604 KB	Output is correct
56	Correct	1 ms	344 KB	Output is correct
57	Correct	1 ms	344 KB	Output is correct
58	Correct	1 ms	348 KB	Output is correct
59	Correct	1 ms	348 KB	Output is correct
60	Correct	0 ms	448 KB	Output is correct
61	Correct	1 ms	348 KB	Output is correct
62	Correct	1 ms	348 KB	Output is correct
63	Correct	1 ms	348 KB	Output is correct
64	Correct	1 ms	348 KB	Output is correct

Subtask #4
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	448 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	1 ms	452 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	1 ms	604 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	1 ms	600 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	1 ms	348 KB	Output is correct
42	Correct	1 ms	344 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	1 ms	600 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	1 ms	348 KB	Output is correct
48	Correct	0 ms	348 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	0 ms	348 KB	Output is correct
52	Correct	1 ms	344 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Correct	1 ms	348 KB	Output is correct
55	Correct	1 ms	604 KB	Output is correct
56	Correct	1 ms	344 KB	Output is correct
57	Correct	1 ms	344 KB	Output is correct
58	Correct	1 ms	348 KB	Output is correct
59	Correct	1 ms	348 KB	Output is correct
60	Correct	0 ms	448 KB	Output is correct
61	Correct	1 ms	348 KB	Output is correct
62	Correct	1 ms	348 KB	Output is correct
63	Correct	1 ms	348 KB	Output is correct
64	Correct	1 ms	348 KB	Output is correct
65	Correct	11 ms	348 KB	Output is correct
66	Incorrect	10 ms	456 KB	Output isn't correct
67	Halted	0 ms	0 KB	-

Subtask #5
0 / 37.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	448 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	0 ms	348 KB	Output is correct
16	Correct	0 ms	348 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	344 KB	Output is correct
23	Correct	0 ms	348 KB	Output is correct
24	Correct	0 ms	348 KB	Output is correct
25	Correct	0 ms	348 KB	Output is correct
26	Correct	0 ms	348 KB	Output is correct
27	Correct	1 ms	348 KB	Output is correct
28	Correct	0 ms	348 KB	Output is correct
29	Correct	0 ms	348 KB	Output is correct
30	Correct	0 ms	348 KB	Output is correct
31	Correct	0 ms	348 KB	Output is correct
32	Correct	0 ms	348 KB	Output is correct
33	Correct	1 ms	452 KB	Output is correct
34	Correct	0 ms	348 KB	Output is correct
35	Correct	1 ms	604 KB	Output is correct
36	Correct	0 ms	348 KB	Output is correct
37	Correct	0 ms	348 KB	Output is correct
38	Correct	0 ms	348 KB	Output is correct
39	Correct	1 ms	600 KB	Output is correct
40	Correct	0 ms	348 KB	Output is correct
41	Correct	1 ms	348 KB	Output is correct
42	Correct	1 ms	344 KB	Output is correct
43	Correct	0 ms	348 KB	Output is correct
44	Correct	0 ms	348 KB	Output is correct
45	Correct	1 ms	600 KB	Output is correct
46	Correct	0 ms	348 KB	Output is correct
47	Correct	1 ms	348 KB	Output is correct
48	Correct	0 ms	348 KB	Output is correct
49	Correct	0 ms	348 KB	Output is correct
50	Correct	0 ms	348 KB	Output is correct
51	Correct	0 ms	348 KB	Output is correct
52	Correct	1 ms	344 KB	Output is correct
53	Correct	1 ms	348 KB	Output is correct
54	Correct	1 ms	348 KB	Output is correct
55	Correct	1 ms	604 KB	Output is correct
56	Correct	1 ms	344 KB	Output is correct
57	Correct	1 ms	344 KB	Output is correct
58	Correct	1 ms	348 KB	Output is correct
59	Correct	1 ms	348 KB	Output is correct
60	Correct	0 ms	448 KB	Output is correct
61	Correct	1 ms	348 KB	Output is correct
62	Correct	1 ms	348 KB	Output is correct
63	Correct	1 ms	348 KB	Output is correct
64	Correct	1 ms	348 KB	Output is correct
65	Correct	11 ms	348 KB	Output is correct
66	Incorrect	10 ms	456 KB	Output isn't correct
67	Halted	0 ms	0 KB	-

Submission #1066674

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 12.0 / 12.0

Subtask #3 23.0 / 23.0

Subtask #4 0 / 21.0

Subtask #5 0 / 37.0

Subtask #1
7.0 / 7.0

Subtask #2
12.0 / 12.0

Subtask #3
23.0 / 23.0

Subtask #4
0 / 21.0

Subtask #5
0 / 37.0