oj.uz

Submission #80674

# Submission time Handle Problem Language Result Execution time Memory
80674 2018-10-22T02:25:14 Z FutymyClone Paths (BOI18_paths) C++14
100 / 100
 661 ms 173388 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 5;

int n, m, k, a[N];
long long dp[N][32];
vector <int> g[N];

int main(){
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) dp[i][1 << (a[i] - 1)] = 1;
    for (int i = 1; i < 32; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[j][i]) {
                for (auto v: g[j]) {
                    if (i & (1 << (a[v] - 1))) continue;
                    dp[v][i | (1 << (a[v] - 1))] += dp[j][i];
                }
            }
        }
    }

    long long ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j < 32; j++) ans += dp[i][j];
    printf("%lld", ans - n);
    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:13:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
                                  ~~~~~^~~~~~~~~~~~~
paths.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7460 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7664 KB Output is correct
4 Correct 8 ms 7696 KB Output is correct
5 Correct 8 ms 7696 KB Output is correct
6 Correct 8 ms 7696 KB Output is correct
7 Correct 8 ms 7696 KB Output is correct
8 Correct 8 ms 7696 KB Output is correct
9 Correct 9 ms 7832 KB Output is correct
10 Correct 9 ms 7832 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 15432 KB Output is correct
2 Correct 95 ms 16468 KB Output is correct
3 Correct 530 ms 102132 KB Output is correct
4 Correct 141 ms 102132 KB Output is correct
5 Correct 145 ms 102132 KB Output is correct
6 Correct 394 ms 102132 KB Output is correct
7 Correct 524 ms 117292 KB Output is correct
8 Correct 577 ms 122588 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7460 KB Output is correct
2 Correct 9 ms 7552 KB Output is correct
3 Correct 9 ms 7664 KB Output is correct
4 Correct 8 ms 7696 KB Output is correct
5 Correct 8 ms 7696 KB Output is correct
6 Correct 8 ms 7696 KB Output is correct
7 Correct 8 ms 7696 KB Output is correct
8 Correct 8 ms 7696 KB Output is correct
9 Correct 9 ms 7832 KB Output is correct
10 Correct 9 ms 7832 KB Output is correct
11 Correct 127 ms 15432 KB Output is correct
12 Correct 95 ms 16468 KB Output is correct
13 Correct 530 ms 102132 KB Output is correct
14 Correct 141 ms 102132 KB Output is correct
15 Correct 145 ms 102132 KB Output is correct
16 Correct 394 ms 102132 KB Output is correct
17 Correct 524 ms 117292 KB Output is correct
18 Correct 577 ms 122588 KB Output is correct
19 Correct 121 ms 122588 KB Output is correct
20 Correct 92 ms 122588 KB Output is correct
21 Correct 584 ms 131328 KB Output is correct
22 Correct 146 ms 131328 KB Output is correct
23 Correct 155 ms 131328 KB Output is correct
24 Correct 386 ms 131328 KB Output is correct
25 Correct 587 ms 146764 KB Output is correct
26 Correct 609 ms 151892 KB Output is correct
27 Correct 105 ms 151892 KB Output is correct
28 Correct 139 ms 151892 KB Output is correct
29 Correct 661 ms 160884 KB Output is correct
30 Correct 391 ms 160884 KB Output is correct
31 Correct 403 ms 160884 KB Output is correct
32 Correct 630 ms 173388 KB Output is correct
33 Correct 8 ms 173388 KB Output is correct
34 Correct 8 ms 173388 KB Output is correct
35 Correct 8 ms 173388 KB Output is correct
36 Correct 8 ms 173388 KB Output is correct
37 Correct 8 ms 173388 KB Output is correct
38 Correct 8 ms 173388 KB Output is correct
39 Correct 8 ms 173388 KB Output is correct
40 Correct 8 ms 173388 KB Output is correct
41 Correct 8 ms 173388 KB Output is correct
42 Correct 8 ms 173388 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 173388 KB Output is correct
2 Correct 50 ms 173388 KB Output is correct
3 Correct 35 ms 173388 KB Output is correct
4 Correct 136 ms 173388 KB Output is correct
5 Correct 115 ms 173388 KB Output is correct
6 Correct 160 ms 173388 KB Output is correct
7 Correct 39 ms 173388 KB Output is correct
8 Correct 154 ms 173388 KB Output is correct
9 Correct 119 ms 173388 KB Output is correct
10 Correct 128 ms 173388 KB Output is correct
11 Correct 96 ms 173388 KB Output is correct
12 Correct 106 ms 173388 KB Output is correct
13 Correct 103 ms 173388 KB Output is correct
14 Correct 152 ms 173388 KB Output is correct
15 Correct 146 ms 173388 KB Output is correct
16 Correct 8 ms 173388 KB Output is correct
17 Correct 8 ms 173388 KB Output is correct
18 Correct 8 ms 173388 KB Output is correct
19 Correct 8 ms 173388 KB Output is correct
20 Correct 8 ms 173388 KB Output is correct
21 Correct 8 ms 173388 KB Output is correct
22 Correct 8 ms 173388 KB Output is correct
23 Correct 8 ms 173388 KB Output is correct
24 Correct 8 ms 173388 KB Output is correct
25 Correct 8 ms 173388 KB Output is correct