Submission #203794

#	Time	Username	Problem	Language	Result	Execution time	Memory
203794		dndhk	Amusement Park (CEOI19_amusementpark)	C++14	19 / 100	3083 ms	167924 KiB

amusementpark

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MAX_N = 30;
const ll MOD = 998244353;

int N, M;
vector<int> gp[MAX_N+1];
vector<pii> edge;
int c[MAX_N+1], idx[MAX_N+1];
ll ans;

set<ll> st;
ll chk(){
	for(int i=1; i<=N; i++)	while(!gp[i].empty())	gp[i].pop_back();
	ll now = 0;
	for(int i=0; i<M; i++){
		now = (now << 1);
		int u = edge[i].first, v = edge[i].second;
		if(idx[u]<idx[v]){
			int t = u; u = v; v = t;
			now+=1LL;
		}
		gp[u].pb(v);
	}
	if(st.find(now)!=st.end())	return 0;
	//cout<<now<<endl;
	st.insert(now); return now;
}

int per[MAX_N+1];

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++){
		int x, y; scanf("%d%d", &x, &y); edge.pb({x, y});
	}
	for(int i=0; i<N; i++){
		per[i] = i+1;
	}
	while(1){
		for(int i=0; i<N; i++)	idx[per[i]] = i;
		ans = (ans + __builtin_popcountll(chk())) % MOD;
		if(!next_permutation(per, per+N))	break;
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:40: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:42:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y); edge.pb({x, y});
             ~~~~~^~~~~~~~~~~~~~~~

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