oj.uz

Submission #492250

# Submission time Handle Problem Language Result Execution time Memory
492250 2021-12-06T08:09:37 Z Haruto810198 Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 9 ms 15108 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 270000;
const int inv2 = (mod + 1) / 2;

int n, m;
bool edge[18][18];
int Nc[18];
int sz;
unordered_map<int, int> dp[MAX];

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n>>m;
	sz = (1<<n);
	FOR(i, 1, m, 1){
		int u, v;
		cin>>u>>v;
		u--, v--;
		edge[u][v] = edge[v][u] = 1;
	}
	
	FOR(i, 0, n-1, 1){
		FOR(j, 0, n-1, 1){
			if(edge[i][j]) Nc[i] |= (1<<j);
		}
	}
	
	FOR(v, 0, n-1, 1){
		dp[(1<<v)][sz - 1 - (1<<v)] = 1;
	}

	FOR(A, 1, sz-1, 1){
		int IA = sz - 1 - A;
		for(int B = IA; B > 0; B = ((B-1) & IA)){
			dp[A][B] += 0;
			int AA, BB;
			
			// AA = A U {c};
			// BB = B \ {0, ..., c-1} U {N(c) \ A}
			//cerr<<"dp["<<A<<"]["<<B<<"] = "<<dp[A][B]<<endl;
			FOR(c, 0, n-1, 1){
				if((B & (1<<c)) == 0) continue;
				AA = A | (1<<c);
				BB = B & (~(1<<c));
				BB |= (Nc[c] & (~A));
				dp[AA][BB] += dp[A][B];
				dp[AA][BB] %= mod;
				//cerr<<"dp["<<AA<<"]["<<BB<<"] += "<<dp[A][B]<<endl;
			}
		}
	}
	
	//cerr<<"ways = "<<dp[sz-1][0]<<endl;
	int res = (dp[sz-1][0] * ((m * inv2) % mod)) % mod;
	cout<<res<<'\n';

    return 0;

}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 37.0

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