# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
781128 | definitelynotmee | Amusement Park (CEOI19_amusementpark) | C++17 | 3069 ms | 6484 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const ll MOD = 998244353;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<int> adj(n);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
a--, b--;
adj[a]+=1<<b;
}
vector<ll> incomp(1<<n);
for(int i = 0; i < (1<<n); i++){
int ok = 0;
for(int j = 0; j < n; j++){
if((1<<j)&i){
ok|=adj[j];
}
}
incomp[i] = !bool(ok&i);
// cerr << bitset<4>(ok) << ' ' << bitset<4>(i) << "->" << incomp[i] << '\n';
}
vector<ll> sum(1<<n), dp(1<<n);
dp[0] = 1;
array<ll,2> parity = {MOD-1,1};
vector<int> cur;
auto calc =[&](int i, int taken, int cursum, int sub, int mask, auto calc){
if(i == cur.size()){
if(!taken)
return;
const int comp = mask^sub;
dp[mask]+=parity[taken&1]*dp[comp];
sum[mask]+=parity[taken&1]*(cursum*dp[comp]%MOD+sum[comp]);
dp[mask]%=MOD;
sum[mask]%=MOD;
// cerr << i << ' ' << taken << ' ' << cursum << ' ' << bitset<4>(sub) << ' ' << bitset<4>(mask) << '\n';
// cerr << "=> " << parity[taken&1]*dp[comp] << ' ' << parity[taken&1]*(cursum*dp[comp]%MOD+sum[comp]) << '\n';
return;
}
const int id = cur[i];
if(incomp[sub|(1<<id)]){
calc(i+1,taken+1,cursum+__builtin_popcount(adj[id]&mask),sub|(1<<id),mask,calc);
}
calc(i+1,taken,cursum,sub,mask,calc);
};
for(int mask = 1; mask < (1<<n); mask++){
cur.clear();
for(int j = 0 ; j < n; j++){
if(mask&(1<<j))
cur.push_back(j);
}
calc(0,0,0,0,mask,calc);
// cerr << "dp[" << bitset<4>(mask) << "] = " << dp[mask] << '\n';
// cerr << "sum[" << bitset<4>(mask) << "] = " << sum[mask] << '\n';
}
cout << sum[(1<<n)-1] << '\n';
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |