oj.uz

Submission #741806

# Submission time Handle Problem Language Result Execution time Memory
741806 2023-05-15T00:35:22 Z nishkarsh Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 1 ms 308 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 18;
const int mod = 998244353;
ll ways[1<<N][N];
ll ways2[1<<N];
int undirected_edge[N];
int main(){
	int n,m,a,b;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		a--;b--;
		undirected_edge[a] ^= (1<<b);
		undirected_edge[b] ^= (1<<a);
	}
	for(int i = 0; i < n; i++){
		ways[1<<i][i] = 1;
		ways2[1<<i] = 1;
	}
	for(int i = 0; i < (1<<n); i++){
		if(! (i&(i-1))) continue;
		for(int j = 0; j < n; j++){
			if(! (i&(1<<j))) continue;
			ways[i][j] = ways2[i^(1<<j)];
			for(int k = 0; k < n; k++){
				if((! (i&(1<<j))) || (k == j)) continue;
				if((! (undirected_edge[j]&(1<<k))) && (k < j)){
					ways[i][j] -= ways[i^(1<<k)][j];
					if(ways[i][j] < 0) ways[i][j] += mod;
				}
			}
			ways[i][j] %= mod;
			ways2[i] += ways[i][j];
		}
		ways2[i] %= mod;
	}
	ll ans = ways2[(1<<n)-1];
	if(ans&1) ans += mod;
	ans >>= 1;
	ans *= m; ans %= mod;
	cout << ans;
	return 0;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 308 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 308 KB Output isn't correct
4 Halted 0 ms 0 KB -