oj.uz

Submission #211232

# Submission time Handle Problem Language Result Execution time Memory
211232 2020-03-19T15:33:12 Z Lawliet Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 81 ms 164472 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164472 KB Output is correct
2 Correct 77 ms 164448 KB Output is correct
3 Incorrect 81 ms 164472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164472 KB Output is correct
2 Correct 77 ms 164448 KB Output is correct
3 Incorrect 81 ms 164472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164472 KB Output is correct
2 Correct 77 ms 164448 KB Output is correct
3 Incorrect 81 ms 164472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164472 KB Output is correct
2 Correct 77 ms 164448 KB Output is correct
3 Incorrect 81 ms 164472 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 164472 KB Output is correct
2 Correct 77 ms 164448 KB Output is correct
3 Incorrect 81 ms 164472 KB Output isn't correct
4 Halted 0 ms 0 KB -