oj.uz

Submission #873900

# Submission time Handle Problem Language Result Execution time Memory
873900 2023-11-16T02:37:12 Z noiaint Paths (BOI18_paths) C++17
100 / 100
 487 ms 100560 KB 
#include <bits/stdc++.h>
#define int long long

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 3e5 + 5;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n, m, k;
vector<int> adj[N];
int a[N];
int f[N][1 << 5];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        --a[i];
    }
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 0; i < n; ++i) {
        f[i][1 << a[i]] = 1;
    }
    for (int mask = 0; mask < bit(k); ++mask) {
        for (int i = 0; i < k; ++i) if (getbit(mask, i)) {
            for (int u = 0; u < n; ++u) {
                for (int v : adj[u]) if (a[v] == i) {
                    f[v][mask] += f[u][mask ^ bit(i)];
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; ++i) for (int mask = 0; mask < bit(k); ++mask) {
        res += f[i][mask];
    }

    cout << res - n << '\n';

    return 0;
}

/*

*/

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10944 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10952 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10952 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 23120 KB Output is correct
2 Correct 64 ms 22352 KB Output is correct
3 Correct 266 ms 99836 KB Output is correct
4 Correct 81 ms 30668 KB Output is correct
5 Correct 65 ms 30628 KB Output is correct
6 Correct 182 ms 75328 KB Output is correct
7 Correct 259 ms 99744 KB Output is correct
8 Correct 279 ms 100560 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 2 ms 10944 KB Output is correct
6 Correct 2 ms 10844 KB Output is correct
7 Correct 2 ms 10844 KB Output is correct
8 Correct 2 ms 10952 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 10952 KB Output is correct
11 Correct 76 ms 23120 KB Output is correct
12 Correct 64 ms 22352 KB Output is correct
13 Correct 266 ms 99836 KB Output is correct
14 Correct 81 ms 30668 KB Output is correct
15 Correct 65 ms 30628 KB Output is correct
16 Correct 182 ms 75328 KB Output is correct
17 Correct 259 ms 99744 KB Output is correct
18 Correct 279 ms 100560 KB Output is correct
19 Correct 74 ms 23024 KB Output is correct
20 Correct 74 ms 22456 KB Output is correct
21 Correct 292 ms 99980 KB Output is correct
22 Correct 83 ms 30616 KB Output is correct
23 Correct 65 ms 30800 KB Output is correct
24 Correct 190 ms 75196 KB Output is correct
25 Correct 268 ms 99848 KB Output is correct
26 Correct 257 ms 100432 KB Output is correct
27 Correct 100 ms 22424 KB Output is correct
28 Correct 121 ms 24400 KB Output is correct
29 Correct 473 ms 99980 KB Output is correct
30 Correct 377 ms 62916 KB Output is correct
31 Correct 326 ms 62724 KB Output is correct
32 Correct 487 ms 100148 KB Output is correct
33 Correct 2 ms 10840 KB Output is correct
34 Correct 2 ms 10844 KB Output is correct
35 Correct 2 ms 10844 KB Output is correct
36 Correct 2 ms 10844 KB Output is correct
37 Correct 2 ms 10844 KB Output is correct
38 Correct 2 ms 10844 KB Output is correct
39 Correct 2 ms 10844 KB Output is correct
40 Correct 2 ms 10844 KB Output is correct
41 Correct 3 ms 10844 KB Output is correct
42 Correct 2 ms 10844 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 54 ms 13916 KB Output is correct
3 Correct 22 ms 13912 KB Output is correct
4 Correct 69 ms 42640 KB Output is correct
5 Correct 47 ms 42952 KB Output is correct
6 Correct 236 ms 42672 KB Output is correct
7 Correct 34 ms 13916 KB Output is correct
8 Correct 120 ms 42580 KB Output is correct
9 Correct 75 ms 43056 KB Output is correct
10 Correct 98 ms 42692 KB Output is correct
11 Correct 133 ms 29132 KB Output is correct
12 Correct 119 ms 35904 KB Output is correct
13 Correct 126 ms 29252 KB Output is correct
14 Correct 232 ms 42568 KB Output is correct
15 Correct 247 ms 42580 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 2 ms 10844 KB Output is correct
18 Correct 2 ms 10948 KB Output is correct
19 Correct 3 ms 10844 KB Output is correct
20 Correct 3 ms 10844 KB Output is correct
21 Correct 3 ms 10840 KB Output is correct
22 Correct 3 ms 10840 KB Output is correct
23 Correct 3 ms 10840 KB Output is correct
24 Correct 2 ms 10844 KB Output is correct
25 Correct 2 ms 10844 KB Output is correct