oj.uz

Submission #741217

# Submission time Handle Problem Language Result Execution time Memory
741217 2023-05-13T21:08:46 Z nishkarsh Amusement Park (CEOI19_amusementpark) C++14
7 / 100
 1 ms 312 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 sum[1<<N][N];
int undirected_edge[N];
int rev_directed_edge[N];
int main(){
	int n,m,a,b;
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a >> b;
		a--;b--;
		rev_directed_edge[b] ^= (1<<a);
		undirected_edge[a] ^= (1<<b);
		undirected_edge[b] ^= (1<<a);
	}
	for(int i = 0; i < n; i++) ways[1<<i][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;
			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<<j)][k];
					sum[i][j] += sum[i^(1<<j)][k];
				}
			}
			ways[i][j] %= mod;
			sum[i][j] += ways[i][j] * __builtin_popcount(rev_directed_edge[j]&i);
			sum[i][j] %= mod;
		}
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) ans += sum[(1<<n)-1][i];
	ans %= mod;
	cout << ans;
	return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 312 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Incorrect 1 ms 312 KB Output isn't correct
10 Halted 0 ms 0 KB -