Submission #211232

#	Time	Username	Problem	Language	Result	Execution time	Memory
211232		Lawliet	Amusement Park (CEOI19_amusementpark)	C++17	0 / 100	81 ms	164472 KiB

amusementpark

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 20;
const int MAXS = 160;
const int MOD = 998244353;
const int EXP = 1024*1024 + 10;

int n, m;

int adj[MAXN];

lli dp[EXP][MAXN];

bool isActive(int mask, int v) { return mask & (1 << v); }

lli solve(int mask, int c)
{
	lli& ans = dp[mask][c];

	if( ans != -1 ) return ans;

	if( mask == (1 << n) - 1 ) return c;

	ans = 0;

	for(int i = 0 ; i < n ; i++)
	{
		if( isActive( mask , i ) ) continue;

		int aux = mask & adj[i];
		int newC = c + __builtin_popcount( aux );

		ans += solve( mask + (1 << i) , newC );
	}

	ans %= MOD;

	return ans;
}

int main()
{
	scanf("%d %d",&n,&m);

	memset( dp , -1 , sizeof(dp) );

	for(int i = 1 ; i <= m ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);
		U--; V--;

		adj[V] = adj[V] | (1 << U);
	}

	printf("%lld\n",solve( 0 , 0 ));
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
amusementpark.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~

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