oj.uz

Submission #418139

# Submission time Handle Problem Language Result Execution time Memory
418139 2021-06-05T07:03:09 Z tengiz05 Paths (BOI18_paths) C++17
100 / 100
 2061 ms 233796 KB 
#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 3e5 + 5;
int n, m, k;
int dp[6][N][32], a[N];
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
        dp[0][i][1 << a[i]] = 1;
    }
    std::vector<std::pair<int, int>> e(m);
    for (auto &[u, v] : e) {
        std::cin >> u >> v;
        u--;
        v--;
    }
    for (int K = 1; K < 6; K++) {
        for (int msk = 1; msk < 32; msk++) {
            for (auto [u, v] : e) {
                if (!(msk & (1 << a[u])) || !(msk & (1 << a[v]))) continue;
                dp[K][u][msk] += dp[K - 1][v][msk ^ (1 << a[u])];
                dp[K][v][msk] += dp[K - 1][u][msk ^ (1 << a[v])];
            }
        }
    }
    i64 ans = 0;
    for (int K = 1; K < 6; K++) {
        for (int msk = 1; msk < 32; msk++) {
            for (int i = 0; i < n; i++) {
                ans += dp[K][i][msk];
            }
        }
    }
    std::cout << ans << "\n";
    return 0;
}

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 7524 KB Output is correct
2 Correct 422 ms 4416 KB Output is correct
3 Correct 1884 ms 230476 KB Output is correct
4 Correct 836 ms 26464 KB Output is correct
5 Correct 893 ms 26540 KB Output is correct
6 Correct 1474 ms 154976 KB Output is correct
7 Correct 1919 ms 230540 KB Output is correct
8 Correct 1951 ms 230416 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 440 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 372 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 471 ms 7524 KB Output is correct
12 Correct 422 ms 4416 KB Output is correct
13 Correct 1884 ms 230476 KB Output is correct
14 Correct 836 ms 26464 KB Output is correct
15 Correct 893 ms 26540 KB Output is correct
16 Correct 1474 ms 154976 KB Output is correct
17 Correct 1919 ms 230540 KB Output is correct
18 Correct 1951 ms 230416 KB Output is correct
19 Correct 478 ms 9192 KB Output is correct
20 Correct 422 ms 5564 KB Output is correct
21 Correct 1911 ms 233756 KB Output is correct
22 Correct 855 ms 28720 KB Output is correct
23 Correct 919 ms 28648 KB Output is correct
24 Correct 1449 ms 158020 KB Output is correct
25 Correct 2061 ms 233776 KB Output is correct
26 Correct 2017 ms 233724 KB Output is correct
27 Correct 454 ms 5508 KB Output is correct
28 Correct 522 ms 11504 KB Output is correct
29 Correct 1993 ms 233736 KB Output is correct
30 Correct 1356 ms 119972 KB Output is correct
31 Correct 1361 ms 119860 KB Output is correct
32 Correct 1981 ms 233796 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 1 ms 332 KB Output is correct
38 Correct 1 ms 332 KB Output is correct
39 Correct 1 ms 316 KB Output is correct
40 Correct 1 ms 444 KB Output is correct
41 Correct 1 ms 320 KB Output is correct
42 Correct 1 ms 332 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 155 ms 2112 KB Output is correct
3 Correct 141 ms 2168 KB Output is correct
4 Correct 577 ms 77920 KB Output is correct
5 Correct 488 ms 78012 KB Output is correct
6 Correct 555 ms 78044 KB Output is correct
7 Correct 148 ms 2116 KB Output is correct
8 Correct 536 ms 77916 KB Output is correct
9 Correct 475 ms 77944 KB Output is correct
10 Correct 452 ms 78020 KB Output is correct
11 Correct 314 ms 39856 KB Output is correct
12 Correct 391 ms 59064 KB Output is correct
13 Correct 320 ms 40004 KB Output is correct
14 Correct 538 ms 78016 KB Output is correct
15 Correct 528 ms 78020 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 320 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct