oj.uz

Submission #211236

# Submission time Handle Problem Language Result Execution time Memory
211236 2020-03-19T16:05:04 Z Lawliet Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 5 ms 384 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 sz;

int inv[MAXN];
int fat[MAXN];
int adj[MAXN][MAXN];

bool marc[MAXN];

lli dp[EXP][MAXN];

vector< int > curNodes;

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 << sz) - 1 ) return c;

	ans = 0;

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

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

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

	ans %= MOD;

	return ans;
}

lli invMod(int k)
{
	if( k == 1 ) return 1;

	lli ans = ( MOD - MOD/k );
	ans *= invMod( MOD%k );

	return ans%MOD;
}

void DFS(int cur)
{
	marc[cur] = true;
	curNodes.push_back( cur );

	for(int i = 0 ; i < n ; i++)
		if( !marc[i] && ( adj[cur][i] || adj[i][cur] ) )DFS( i );
}

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

	fat[0] = 1;

	for(int i = 1 ; i <= n ; i++)
	{
		fat[i] = fat[i - 1]*i;
		fat[i] %= MOD;
	}

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

		adj[U][V] = true;
	}

	vector< int > allSz;
	vector< lli > allDP;

	for(int i = 0 ; i < n ; i++)
	{
		if( marc[i] ) continue;

		DFS( i );

		sz = curNodes.size();

		for(int mask = 0 ; mask < (1 << sz) ; mask++)
			for(int j = 0 ; j < MAXS ; j++)
				dp[mask][j] = -1;

		for(int j = 0 ; j < curNodes.size() ; j++)
			inv[j] = 0;

		for(int a = 0 ; a < curNodes.size() ; a++)
		{
			for(int b = 0 ; b < curNodes.size() ; b++)
			{
				if( a == b ) continue;

				int curA = curNodes[a];
				int curB = curNodes[b];

				if( adj[curA][curB] ) inv[a] += ( 1 << b );
			}
		}

		allSz.push_back( sz );
		allDP.push_back( solve( 0 , 0 ) );

		curNodes.clear();
	}

	lli p = 1;	
	lli ans = 0;

	for(int i = 0 ; i < allSz.size() ; i++)
	{
		p *= fat[ allSz[i] ];
		p %= MOD;
	}

	for(int i = 0 ; i < allDP.size() ; i++)
	{
		lli c = p;
		c *= invMod( fat[ allSz[i] ] );

		c %= MOD;
		c *= allDP[i];
		c %= MOD;

		ans += c;
	}

	printf("%lld\n",ans%MOD);
}

Compilation message

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:106:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < curNodes.size() ; j++)
                   ~~^~~~~~~~~~~~~~~~~
amusementpark.cpp:109:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int a = 0 ; a < curNodes.size() ; a++)
                   ~~^~~~~~~~~~~~~~~~~
amusementpark.cpp:111:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int b = 0 ; b < curNodes.size() ; b++)
                    ~~^~~~~~~~~~~~~~~~~
amusementpark.cpp:131:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < allSz.size() ; i++)
                  ~~^~~~~~~~~~~~~~
amusementpark.cpp:137:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < allDP.size() ; i++)
                  ~~^~~~~~~~~~~~~~
amusementpark.cpp:72: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:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~
amusementpark.cpp:104:17: warning: iteration 20 invokes undefined behavior [-Waggressive-loop-optimizations]
     dp[mask][j] = -1;
     ~~~~~~~~~~~~^~~~
amusementpark.cpp:103:22: note: within this loop
    for(int j = 0 ; j < MAXS ; j++)
                    ~~^~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 5 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -