Submission #650377

#	Time	Username	Problem	Language	Result	Execution time	Memory
650377		daria	Amusement Park (CEOI19_amusementpark)	C++14	100 / 100	2573 ms	4556 KiB

amusementpark

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define _ << " " <<
typedef pair<int, int> pii;
typedef array<int, 3> tii;

const int inf = 1e9;
const ll INF = 1e18;
const ll mod = 998244353;

int main(){
 int n, m; cin >> n >> m;
 const int N = (1 << n);
 vector<vector<bool> > adj(n, vector<bool> (n, 0));
 vector<ll> cnt(N, 0), res(N, 0);
 for(int i = 0; i<m; ++i){
  int a, b; cin >> a >> b; a--; b--;
  adj[a][b] = adj[b][a] = 1;
 }
 vector<bool> indset(N, 1);
 for(int i=0; i<N; ++i)
  for(int j=0; j<n; ++j)
   cnt[i] += (!!((1<<j)&i));
 for(int i=0; i<N; ++i)
  for(int j=0; j<min(n, i); ++j)
   for(int k=0; k<j; ++k)
    if(adj[j][k] & !!(1&(i>>j)) & !!(1&(i>>k)))
     indset[i] = 0;
 res[0] = 1;
 for(int i=1; i<N; ++i){
  for(int j = i; j; j = (i&(j-1))){
   if(cnt[j]%2) res[i] = (res[i] + indset[j]*res[i^j])%mod;
   else res[i] = (res[i] + mod - indset[j]*res[i^j])%mod;
  }
 }
 ll ans = ((res[N-1] + mod)*m)%mod;
 ans = (ans*(mod+1)/2)%mod;
 cout << ans << endl;
}

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