Submission #1055663

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055663		coolsentenceidontremember	Amusement Park (CEOI19_amusementpark)	C++17	100 / 100	1309 ms	2904 KiB

amusementpark

#include<bits/stdc++.h>

#pragma GCC optimize("O3", "unroll-loops")


#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"
#define precision(x) fixed << setprecision((x))
#define check_ok() cout << "it aight" << '\n'
using namespace std;



void setIO(string s = ""){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 if (!s.empty()){
	freopen((s+".in").c_str(), "r", stdin);
	freopen((s+".out").c_str(), "w", stdout);
	}
}

const int N = 18;
const ll mod = 998244353;
const ll two_inv = 499122177;
bool ind[1<<N];
int adj[N];
ll dp[1<<N];




int main(){
  int n, m;
  cin >> n >> m;
  memset(adj, 0, sizeof adj);
  fill(ind, ind + (1<<n), 1);
  for (int i = 1; i <= m; i++){
  	int u, v;
  	cin >> u >> v;
  	u--; v--;
  	adj[u] |= (1<<v);
  	ind[(1<<u)|(1<<v)] = 0;
  }
  for (int mask = 1; mask < (1<<n); mask++){
  	for (int b = 0; b < n; b++){
  		if (mask & (1<<b) && !ind[mask^(1<<b)]){
  			ind[mask] = 0;
  			break;
		  }
	  }
  }
  memset(dp, 0, sizeof dp);
  dp[0] = 1;
  for (int mask = 1; mask < (1<<n); mask++){
  	for (int subset = mask; subset; subset = (subset-1)&mask){
  		if (ind[subset]){
  			int bc = __builtin_popcount(subset);
  			if (bc&1) dp[mask] = (dp[mask]+dp[mask^subset])%mod;
  			else dp[mask] = (dp[mask]-dp[mask^subset]+mod)%mod;
  			
		  }
	  }
  }
  int full = (1<<n)-1;
  dp[full] = (dp[full]+mod)%mod;
  ll ans = dp[full]*m%mod*two_inv%mod;
 // for (int mask = 0; mask < (1<<n); mask++) cout << mask << ' ' << ind[mask] << '\n';
  cout << ans;
  
}
                 

Compilation message (stderr)

amusementpark.cpp: In function 'void setIO(std::string)':
amusementpark.cpp:25:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
amusementpark.cpp:26:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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