oj.uz

Submission #199999

# Submission time Handle Problem Language Result Execution time Memory
199999 2020-02-04T17:20:31 Z davitmarg Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 3000 ms 376 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;
 
LL binpow(LL a,int n)
{
	if(n==0)
		return 1;
	if(n%2==0)
		return binpow(a*a%mod,n/2);
	return a*binpow(a,n-1)%mod;
}
 
bool inMask(int a,int mask)
{
	return (bool)((1<<a)&mask);
}
 
int n,m;
int ans[(1<<18)+10],cnt[(1<<18)+10];
vector<pair<int,int>> p;
vector<int> g[20];
bool isEdge[(1<<18)+10];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		g[a].PB(b);
		g[b].PB(a);
		p.PB(MP(a,b));
	}
	//for(int i=0;i<n;i++)
	//	ans[(1<<i)]=1;
 
	for(int mask=0;mask<(1<<n);mask++)
	{
		for(int i=0;i<n;i++)
		{
			if(((1<<i)&mask)==0)
				continue;
			cnt[mask]++;
			for(int j=0;j<g[i].size();j++)
				isEdge[mask]|=inMask(g[i][j],mask);
		}
		//cout<<"cnt["<<mask<<"]="<<cnt[mask]<<endl;
	}
	ans[0]=1;
	for(int mask=1;mask<(1<<n);mask++)
	{
		int s=mask;
		while(s>0)
		{
 
			if(isEdge[s])
				continue;
 
			//cout<<"cnt["<<(mask^s)<<"]="<<cnt[mask^s]<<endl;
			//cout<<"!ns["<<(mask^s)<<"]="<<ans[mask^s]<<endl;
			if(cnt[s]%2==1)
				ans[mask]+=ans[mask^s];
			else
				ans[mask]+=mod-ans[mask^s];
			ans[mask]%=mod;
			s=(s-1)&mask;
		}
 
		//cout<<"ans["<<mask<<"]="<<ans[mask]<<endl;
	}
 
	LL answ=ans[(1<<n)-1];
	answ*=(LL)m;
	answ%=mod;
	answ*=binpow(2,mod-2);
	answ%=mod;
 
	cout<<answ<<endl;
 
	return 0;
}
 
/*
 
3 1
1 2
 
 
 
*/

Compilation message

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<g[i].size();j++)
                ~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 3075 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 3075 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 3075 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 3075 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Execution timed out 3075 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -