oj.uz

Submission #407434

# Submission time Handle Problem Language Result Execution time Memory
407434 2021-05-19T00:13:59 Z CrouchingDragon Amusement Park (CEOI19_amusementpark) C++17
7 / 100
 34 ms 74188 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, nmax = 18;
using mint = Mint<mod>;

mint sum[1 << nmax][nmax], cnt[1 << nmax][nmax];

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

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

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

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

    for (int u = 0; u < n; ++u) cnt[1 << u][u] = 1;

    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int u = 0; u < n; ++u) {
            if (mask >> u & 1) continue;
            int nmask = mask | 1 << u;
            for (int v = 0; v < n; ++v) {
                if (not ((E[v] >> u & 1) || (E[u] >> v & 1) || u > v)) continue;
                cnt[nmask][u] += cnt[mask][v];
                sum[nmask][u] += sum[mask][v] + cnt[mask][v] * popcount[E[u] & mask];
            }
        }

    }

    mint ans = 0;
    for (int u = 0; u < n; ++u) ans += sum[(1 << n) - 1][u];

    cout << ans << endl;

    exit(0);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74052 KB Output is correct
2 Correct 34 ms 74188 KB Output is correct
3 Correct 34 ms 74096 KB Output is correct
4 Correct 33 ms 74068 KB Output is correct
5 Correct 33 ms 74096 KB Output is correct
6 Correct 33 ms 74044 KB Output is correct
7 Correct 34 ms 74128 KB Output is correct
8 Correct 34 ms 74112 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74052 KB Output is correct
2 Correct 34 ms 74188 KB Output is correct
3 Correct 34 ms 74096 KB Output is correct
4 Correct 33 ms 74068 KB Output is correct
5 Correct 33 ms 74096 KB Output is correct
6 Correct 33 ms 74044 KB Output is correct
7 Correct 34 ms 74128 KB Output is correct
8 Correct 34 ms 74112 KB Output is correct
9 Incorrect 34 ms 74064 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74052 KB Output is correct
2 Correct 34 ms 74188 KB Output is correct
3 Correct 34 ms 74096 KB Output is correct
4 Correct 33 ms 74068 KB Output is correct
5 Correct 33 ms 74096 KB Output is correct
6 Correct 33 ms 74044 KB Output is correct
7 Correct 34 ms 74128 KB Output is correct
8 Correct 34 ms 74112 KB Output is correct
9 Incorrect 34 ms 74064 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74052 KB Output is correct
2 Correct 34 ms 74188 KB Output is correct
3 Correct 34 ms 74096 KB Output is correct
4 Correct 33 ms 74068 KB Output is correct
5 Correct 33 ms 74096 KB Output is correct
6 Correct 33 ms 74044 KB Output is correct
7 Correct 34 ms 74128 KB Output is correct
8 Correct 34 ms 74112 KB Output is correct
9 Incorrect 34 ms 74064 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 74052 KB Output is correct
2 Correct 34 ms 74188 KB Output is correct
3 Correct 34 ms 74096 KB Output is correct
4 Correct 33 ms 74068 KB Output is correct
5 Correct 33 ms 74096 KB Output is correct
6 Correct 33 ms 74044 KB Output is correct
7 Correct 34 ms 74128 KB Output is correct
8 Correct 34 ms 74112 KB Output is correct
9 Incorrect 34 ms 74064 KB Output isn't correct
10 Halted 0 ms 0 KB -