oj.uz

Submission #313774

# Submission time Handle Problem Language Result Execution time Memory
313774 2020-10-17T04:25:46 Z jhnah917 Amusement Park (CEOI19_amusementpark) C++14
0 / 100
 1 ms 384 KB 
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;
const int pw_2_15 = 32768;
const int pw_3_18 = 387420489;
const int mod = 998244353;
int pw[22];

int n, m, bit[22];
vector<int> g[22];
map<p, ll> dp;

bool in(int Set, int Elem){
    return (Set & (1 << Elem)) != 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    pw[0] = 1; for(int i=1; i<22; i++) pw[i] = pw[i-1] * 3;
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e; s--; e--;
        g[s].push_back(e); g[e].push_back(s);
        bit[s] |= (1 << e); bit[e] |= (1 << s);
    }
    
    dp[p(0, 0)] = 1;
    for(auto i : dp){
        int a = i.x.x, b = i.x.y; ll cnt = i.y;
        cout << a << " " << b << "\n";
        for(int j=0; j<n; j++) if(!in(a|b, j)) {
            int a_ = (a | (1 << j));
            int b_ = ((b | ((1<<j)-1)) & ~bit[j] & ~a);
            dp[p(a_, b_)] = (cnt + dp[p(a_, b_)]) % mod;
        }
    }
    ll res = dp[p((1<<n)-1, 0)];
    res = res * m % mod * (mod/2+1) % mod;
    cout << res;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -