Submission #203799

#	Time	Username	Problem	Language	Result	Execution time	Memory
203799		dndhk	Amusement Park (CEOI19_amusementpark)	C++14	19 / 100	3088 ms	33544 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;

vector<ll> vt;

set<ll> st;
void 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<<=1LL;
		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);
	}
	vt.pb(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;
		chk();
		if(!next_permutation(per, per+N))	break;
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for(int i=0; i<vt.size(); i++){
		for(int j=0; j<M; j++){
			ans = (ans + (vt[i]%2LL)) % MOD;
			vt[i]/=2LL;
		}
	}
	cout<<ans;
	return 0;
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
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