oj.uz

Submission #485554

# Submission time Handle Problem Language Result Execution time Memory
485554 2021-11-08T08:45:32 Z chungdinh Paths (BOI18_paths) C++17
100 / 100
 430 ms 61344 KB 
#include <iostream>
#include <vector>

#define ll long long

const int N = 5e5 + 5;
const ll MOD = 1e9 + 7;

#define cntbit(x) __builtin_popcount(x)
#define on(b, x) (b & (1 << x))

using namespace std;

int n, m, k;
int c[N];
vector<int> g[N];

ll dp[1 << 5][N];

vector<int> z[100];

int main() {
    #ifdef CHUNGDINH
    freopen("main.inp", "r", stdin);
    #endif // CHUNGDINH

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> c[i]; c[i]--;
        dp[1 << c[i]][i] = 1;
    }
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int b = 1; b < (1 << k); b++) z[cntbit(b)].push_back(b);

    ll res = 0;

    for (int i = 2; i <= k; i++) {
        for (int b : z[i]) {
            for (int u = 1; u <= n; u++) {
                dp[b][u] = 0;
                if (!on(b, c[u])) continue;

                for (int v : g[u]) {
                    if (!on(b, c[v])) continue;
                    dp[b][u] += dp[b ^ (1 << c[u])][v];
                }

                res += dp[b][u];
            }
        }
    }

    cout << res;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12108 KB Output is correct
2 Correct 6 ms 12108 KB Output is correct
3 Correct 6 ms 12048 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12064 KB Output is correct
8 Correct 8 ms 12176 KB Output is correct
9 Correct 6 ms 12048 KB Output is correct
10 Correct 6 ms 12060 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 18796 KB Output is correct
2 Correct 143 ms 17936 KB Output is correct
3 Correct 349 ms 42568 KB Output is correct
4 Correct 179 ms 20564 KB Output is correct
5 Correct 208 ms 20260 KB Output is correct
6 Correct 288 ms 34992 KB Output is correct
7 Correct 368 ms 42436 KB Output is correct
8 Correct 370 ms 43176 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12108 KB Output is correct
2 Correct 6 ms 12108 KB Output is correct
3 Correct 6 ms 12048 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 12052 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 12064 KB Output is correct
8 Correct 8 ms 12176 KB Output is correct
9 Correct 6 ms 12048 KB Output is correct
10 Correct 6 ms 12060 KB Output is correct
11 Correct 181 ms 18796 KB Output is correct
12 Correct 143 ms 17936 KB Output is correct
13 Correct 349 ms 42568 KB Output is correct
14 Correct 179 ms 20564 KB Output is correct
15 Correct 208 ms 20260 KB Output is correct
16 Correct 288 ms 34992 KB Output is correct
17 Correct 368 ms 42436 KB Output is correct
18 Correct 370 ms 43176 KB Output is correct
19 Correct 150 ms 18796 KB Output is correct
20 Correct 138 ms 17936 KB Output is correct
21 Correct 370 ms 42440 KB Output is correct
22 Correct 180 ms 20656 KB Output is correct
23 Correct 193 ms 20188 KB Output is correct
24 Correct 297 ms 35008 KB Output is correct
25 Correct 331 ms 42440 KB Output is correct
26 Correct 361 ms 43072 KB Output is correct
27 Correct 139 ms 17984 KB Output is correct
28 Correct 169 ms 20364 KB Output is correct
29 Correct 430 ms 61344 KB Output is correct
30 Correct 298 ms 40208 KB Output is correct
31 Correct 338 ms 38976 KB Output is correct
32 Correct 422 ms 61316 KB Output is correct
33 Correct 6 ms 12108 KB Output is correct
34 Correct 6 ms 12160 KB Output is correct
35 Correct 7 ms 12108 KB Output is correct
36 Correct 6 ms 11980 KB Output is correct
37 Correct 6 ms 11980 KB Output is correct
38 Correct 6 ms 12108 KB Output is correct
39 Correct 6 ms 12108 KB Output is correct
40 Correct 7 ms 12180 KB Output is correct
41 Correct 6 ms 12108 KB Output is correct
42 Correct 8 ms 12108 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12236 KB Output is correct
2 Correct 59 ms 14140 KB Output is correct
3 Correct 45 ms 13904 KB Output is correct
4 Correct 95 ms 22096 KB Output is correct
5 Correct 92 ms 22808 KB Output is correct
6 Correct 166 ms 41040 KB Output is correct
7 Correct 54 ms 14040 KB Output is correct
8 Correct 115 ms 28356 KB Output is correct
9 Correct 95 ms 29072 KB Output is correct
10 Correct 101 ms 28260 KB Output is correct
11 Correct 107 ms 27504 KB Output is correct
12 Correct 109 ms 33652 KB Output is correct
13 Correct 131 ms 26888 KB Output is correct
14 Correct 174 ms 41020 KB Output is correct
15 Correct 187 ms 41164 KB Output is correct
16 Correct 6 ms 12108 KB Output is correct
17 Correct 6 ms 12108 KB Output is correct
18 Correct 7 ms 12108 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 6 ms 11980 KB Output is correct
21 Correct 8 ms 12080 KB Output is correct
22 Correct 6 ms 12108 KB Output is correct
23 Correct 6 ms 12180 KB Output is correct
24 Correct 7 ms 12108 KB Output is correct
25 Correct 6 ms 11980 KB Output is correct