Submission #699186

#	Time	Username	Problem	Language	Result	Execution time	Memory
699186		vjudge1	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1020 ms	2648 KiB

amusementpark

/* ...... */

#include <bits/stdc++.h>
using namespace std;

#define inl inline
#define all(p) begin (p), end (p)
typedef long long ll;
using pint = pair <int, int>;
#define ctz __builtin_ctz

constexpr int N = 18, P = 998244353;
int n, m, x, y, e[N]; ll f[1<<N]; bool g[1<<N];
vector <pint> l1, l2;

int main () {
	/*  */
	scanf ("%d%d", &n, &m); g[0] = 1;
	for (int i = 1; i <= m; ++i)
		scanf ("%d%d", &x, &y), --x, --y,
		e[x] |= 1<<y, e[y] |= 1<<x;
	for (int s = 1, msk; s < 1<<n; ++s)
		x = ctz (s), msk = s ^ (1<<x),
		g[s] = g[msk] && !(e[x] & msk);
	for (int s = 0; s < 1<<n; ++s) {
		(f[s] += g[s]) %= P; int sube = 0, msk;
		for (x = 0; x < n; ++x)
			if ((s >> x) & 1) sube |= e[x];
		sube &= ((1<<n)-1) ^ s;
		msk = sube; while (msk)
			f[s | msk] += f[s] * g[msk] *
				(P - 1 + (__builtin_parity (msk)<<1)) % P,
			(--msk) &= sube;
	}
	printf ("%lld", f[(1<<n)-1] * m % P * (P+1ll>>1) % P);

	return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:35:42: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |  printf ("%lld", f[(1<<n)-1] * m % P * (P+1ll>>1) % P);
      |                                         ~^~~~
amusementpark.cpp:18:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |  scanf ("%d%d", &n, &m); g[0] = 1;
      |  ~~~~~~^~~~~~~~~~~~~~~~
amusementpark.cpp:20:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |   scanf ("%d%d", &x, &y), --x, --y,
      |   ~~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 21 / 21
• Subtask 5: 37 / 37