oj.uz

Submission #407442

# Submission time Handle Problem Language Result Execution time Memory
407442 2021-05-19T00:48:28 Z CrouchingDragon Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 1 ms 204 KB 
#include "bits/stdc++.h"

using namespace std;

#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(x) begin(x), end(x)

using ll = long long;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

template<ll mod>
struct Mint {
    ll x;
    Mint(ll x = 0) : x((x %= mod) < 0 ? x + mod : x) { }
    Mint& operator+=(Mint rhs) { return (x += rhs.x) >= mod ? x -= mod : 0, *this; }
    Mint& operator-=(Mint rhs) { return (x -= rhs.x) < 0 ? x += mod : 0, *this; }
    Mint& operator*=(Mint rhs) { return (x *= rhs.x) %= mod, *this; }
    Mint& operator/=(Mint rhs) { return *this *= rhs.power(-1); }
    Mint power(ll p) const {
        p %= mod - 1;
        if (p < 0) p += mod - 1;
        Mint res = 1;
        for (Mint y = *this; p; p >>= 1, y *= y) if (p & 1) res *= y;
        return res;
    }
    bool operator==(Mint rhs) const { return x == rhs.x; }
    bool operator<(Mint rhs) const { return x < rhs.x; }
    friend Mint operator+(Mint lhs, Mint rhs) { return lhs += rhs; }
    friend Mint operator-(Mint lhs, Mint rhs) { return lhs -= rhs; }
    friend Mint operator*(Mint lhs, Mint rhs) { return lhs *= rhs; }
    friend Mint operator/(Mint lhs, Mint rhs) { return lhs /= rhs; }
    friend ostream& operator<<(ostream& out, Mint a) { return out << a.x; }
    friend istream& operator>>(istream& in, Mint& a) {
        ll x;
        in >> x;
        a = Mint(x);
        return in;
    }
};

constexpr ll mod = 998244353;
using mint = Mint<mod>;

struct DSU {
    vector<int> p;
    DSU(int n) : p(n) { iota(all(p), 0); }
    int find(int u) { return p[u] == u ? u : p[u] = find(p[u]); }
    bool is_same(int u, int v) { return find(u) == find(v); }
    void unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return;
        p[v] = u;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> E(n);
    DSU dsu(n);

    for (int j = 0; j < m; ++j) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        E[u] |= 1 << v;
        dsu.unite(u, v);
    }

    vector<int> popcount(1 << n);
    for (int mask = 1; mask < (1 << n); ++mask) {
        popcount[mask] = 1 + popcount[mask & (mask - 1)];
    }

    vector<mint> sum(1 << n), cnt(1 << n);
    cnt[0] = 1;

    for (int mask = 0; mask < (1 << n); ++mask) {
        int neighbors = 0;
        for (int u = 0; u < n; ++u) {
            if (mask >> u & 1) neighbors |= E[u];
        }
        for (int u = 0, last = -1; u < n; ++u) {
            if (mask >> u & 1) continue;
            if ((mask & ((1 << u) - 1)) && (not (E[u] & mask) && not (neighbors >> u & 1))) continue;
            if (last != -1 && not dsu.is_same(u, last)) break;
            last = u;

            int nmask = mask | 1 << u;
            cnt[nmask] += cnt[mask];
            sum[nmask] += sum[mask] + cnt[mask] * popcount[E[u] & mask];
        }
    }

    mint ans = sum.back();
    cout << ans << endl;

    exit(0);
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -