oj.uz

Submission #782189

# Submission time Handle Problem Language Result Execution time Memory
782189 2023-07-13T16:13:28 Z magician Amusement Park (CEOI19_amusementpark) C++14
19 / 100
 7 ms 468 KB 
#include<bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
using namespace std;

const int MAXN = 18;
const int MOD = 998244353;
int N, M;
int adj[MAXN];
int f[MASK(18)][300];

int main() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        //freopen("a.in", "r", stdin); freopen("a.ans", "w", stdout);

        cin >> N >> M;
        for(int i = 0; i < M; i++) {
                int a, b;
                cin >> a >> b;
                a--;
                b--;
                adj[a] ^= MASK(b);
        }

        if(N <= 6)
        {
                vector<pair<int, int>> e;
                for(int i = 0; i < N; i++)
                        for(int j = 0; j < N; j++)
                                if(BIT(adj[i], j))
                                        e.push_back(make_pair(i, j));
                int ans = 0;
                for(int mask = 0; mask < MASK(M); mask++) {
                        vector<int> new_adj(N, 0);
                        for(int i = 0; i < M; i++)
                                if(BIT(mask, i))
                                        new_adj[e[i].second] ^= MASK(e[i].first);
                                else
                                        new_adj[e[i].first] ^= MASK(e[i].second);
                        vector<int> vis(N, 0);
                        bool good = true;
                        function<void(int)> dfs = [&](int u) {
                                if(!good)
                                        return;
                                vis[u] = 1;
                                for(int i = 0; i < N; i++)
                                        if(BIT(new_adj[u], i) && vis[i] == 1) {
                                                good = false;
                                                return;
                                        }
                                for(int i = 0; i < N; i++)
                                        if(BIT(new_adj[u], i) && vis[i] == 0) {
                                                dfs(i);
                                                if(!good)
                                                        return;
                                        }
                                vis[u] = 2;
                        };
                        for(int i = 0; i < N; i++)
                                if(vis[i] == 0)
                                        dfs(i);
                        if(good)
                                (ans += __builtin_popcount(mask)) %= MOD;
                }
                cout << ans;
        }
        else
        {
                f[0][0] = 1;
                for(int i = 0; i < MASK(N); i++) {
                        int cnt = __builtin_popcount(i);
                        for(int j = 0; j < N; j++) {
                                if(BIT(i, j))
                                        continue;
                                int cost = __builtin_popcount(adj[j] & i);
                                for(int k = 0; k <= cnt * (cnt - 1) / 2; k++) {
                                        if(f[i][k] == 0)
                                                continue;
                                        (f[i ^ MASK(j)][k + cost] += f[i][k]) %= MOD;
                                }
                        }
                }
                int ans = 0;
                for(int i = 1; i <= N * (N - 1) / 2; i++) {
                        (ans += 1LL * f[MASK(N) - 1][i] * i % MOD) %= MOD;
                }
                cout << ans;
        }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 7 ms 212 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 7 ms 212 KB Output is correct
25 Incorrect 1 ms 468 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 7 ms 212 KB Output is correct
25 Incorrect 1 ms 468 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 328 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 2 ms 212 KB Output is correct
24 Correct 7 ms 212 KB Output is correct
25 Incorrect 1 ms 468 KB Output isn't correct
26 Halted 0 ms 0 KB -