oj.uz

Submission #703467

# Submission time Handle Problem Language Result Execution time Memory
703467 2023-02-27T12:56:10 Z Cyanmond Amusement Park (CEOI19_amusementpark) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 mod = 998244353;

constexpr int inf = 1 << 20;
void chmin(int &a, int b) {
    if (a > b) a = b;
}

int main() {
    int N, M;
    std::cin >> N >> M;
    std::vector<std::pair<int, int>> slides(M);
    std::vector<std::vector<int>> states(N, std::vector<int>(N));
    for (auto &[a, b] : slides) {
        std::cin >> a >> b;
        --a, --b;
        states[a][b] = 1;
        states[b][a] = 2;
    }
    // n = 15 ?
    std::vector<i64> dp1(1 << N, 0), dp2(1 << N, 0);
    dp1[0] = 1;
    for (int bits = 0; bits < (1 << N); ++bits) {
        for (int nextBit = 0; nextBit < N; ++nextBit) {
            if (bits & (1 << nextBit)) {
                continue;
            }
            const int nextBits = bits | (1 << nextBit);
            // calc cost
            i64 cost = 0;
            for (int i = 0; i < N; ++i) {
                if (not(bits & (1 << i))) {
                    continue;
                }
                if (states[i][nextBit] == 2) {
                    ++cost;
                }
            }
            dp2[nextBits] += dp2[bits] + cost * dp1[bits];
            dp1[nextBits] += dp1[bits];
            dp2[nextBits] %= mod;
            dp1[nextBits] %= mod;
        }
    }
    std::cout << dp2[(1 << N) - 1] % mod << std::endl;
}

Subtask #1
0 / 7.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 37.0

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