oj.uz

Submission #441142

# Submission time Handle Problem Language Result Execution time Memory
441142 2021-07-04T11:42:24 Z Autron Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 9 ms 12604 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define MOD 998244353

int adj[20];
map<int, int> dp[1<<18];

int32_t main(){
	int n, m;
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int a, b;
		cin>>a>>b;
		a--, b--;
		adj[a]|=(1<<b);
		adj[b]|=(1<<a);
	}
	dp[0][(1<<n)-1]=1;
	for(int mask=0;mask<(1<<n);++mask){
		for(auto it:dp[mask]){
			int mask2=it.first;
			int nr=it.second;
			for(int x=0;x<n;++x){
				if(mask2&(1<<x)){
					mask2=mask2&(((1<<n)-1)-((1<<(x+1))-1));
					mask2=mask2|((adj[x]|mask)^mask);
					dp[mask|(1<<x)][mask2]+=nr;
					dp[mask|(1<<x)][mask2]%=MOD;
				}
			}
		}
	}
	int sol=dp[(1<<n)-1][0];
	sol=(sol*m)%MOD;
	sol=(sol*(MOD+1)/2)%MOD;
	cout<<sol<<"\n";
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12492 KB Output is correct
2 Correct 9 ms 12492 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Incorrect 8 ms 12604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12492 KB Output is correct
2 Correct 9 ms 12492 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Incorrect 8 ms 12604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12492 KB Output is correct
2 Correct 9 ms 12492 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Incorrect 8 ms 12604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12492 KB Output is correct
2 Correct 9 ms 12492 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Incorrect 8 ms 12604 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12492 KB Output is correct
2 Correct 9 ms 12492 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Incorrect 8 ms 12604 KB Output isn't correct
5 Halted 0 ms 0 KB -