oj.uz

Submission #236944

# Submission time Handle Problem Language Result Execution time Memory
236944 2020-06-04T05:04:42 Z PeppaPig Paths (BOI18_paths) C++14
100 / 100
 435 ms 97248 KB 
#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 3e5 + 5;

int n, m, k, col[N];
long dp[N][1 << 5], ans;
vector<int> g[N], bit[10];

int main() {
    scanf("%d %d %d", &n, &m, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", col + i);
        --col[i];
        dp[i][1 << col[i]] = 1;
    }
    for(int i = 1, a, b; i <= m; i++) {
        scanf("%d %d", &a, &b);
        g[a].emplace_back(b), g[b].emplace_back(a);
    }
    for(int i = 1; i < (1 << k); i++)
        bit[__builtin_popcount(i)].emplace_back(i);
    for(int i = 2; i <= k; i++) for(int b : bit[i]) for(int u = 1; u <= n; u++) {
        if(b >> col[u] & 1) for(int v : g[u])
            dp[u][b] += dp[v][b ^ (1 << col[u])];
        ans += dp[u][b];
    }
    printf("%lld\n", ans);

    return 0;
}

Compilation message

paths.cpp: In function 'int main()':
paths.cpp:14: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:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", col + i);
         ~~~~~^~~~~~~~~~~~~~~
paths.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7456 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 15096 KB Output is correct
2 Correct 90 ms 13408 KB Output is correct
3 Correct 360 ms 96760 KB Output is correct
4 Correct 149 ms 22776 KB Output is correct
5 Correct 140 ms 22776 KB Output is correct
6 Correct 283 ms 69520 KB Output is correct
7 Correct 361 ms 96504 KB Output is correct
8 Correct 353 ms 97248 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 7456 KB Output is correct
2 Correct 8 ms 7424 KB Output is correct
3 Correct 8 ms 7424 KB Output is correct
4 Correct 8 ms 7424 KB Output is correct
5 Correct 8 ms 7424 KB Output is correct
6 Correct 8 ms 7424 KB Output is correct
7 Correct 8 ms 7424 KB Output is correct
8 Correct 10 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 104 ms 15096 KB Output is correct
12 Correct 90 ms 13408 KB Output is correct
13 Correct 360 ms 96760 KB Output is correct
14 Correct 149 ms 22776 KB Output is correct
15 Correct 140 ms 22776 KB Output is correct
16 Correct 283 ms 69520 KB Output is correct
17 Correct 361 ms 96504 KB Output is correct
18 Correct 353 ms 97248 KB Output is correct
19 Correct 105 ms 15056 KB Output is correct
20 Correct 88 ms 13436 KB Output is correct
21 Correct 344 ms 96504 KB Output is correct
22 Correct 147 ms 22776 KB Output is correct
23 Correct 147 ms 22904 KB Output is correct
24 Correct 271 ms 69608 KB Output is correct
25 Correct 344 ms 96764 KB Output is correct
26 Correct 354 ms 97220 KB Output is correct
27 Correct 92 ms 13304 KB Output is correct
28 Correct 115 ms 16632 KB Output is correct
29 Correct 435 ms 96504 KB Output is correct
30 Correct 302 ms 55528 KB Output is correct
31 Correct 291 ms 55588 KB Output is correct
32 Correct 432 ms 96816 KB Output is correct
33 Correct 9 ms 7424 KB Output is correct
34 Correct 9 ms 7424 KB Output is correct
35 Correct 9 ms 7424 KB Output is correct
36 Correct 9 ms 7424 KB Output is correct
37 Correct 8 ms 7424 KB Output is correct
38 Correct 8 ms 7424 KB Output is correct
39 Correct 8 ms 7424 KB Output is correct
40 Correct 9 ms 7424 KB Output is correct
41 Correct 9 ms 7424 KB Output is correct
42 Correct 8 ms 7424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7424 KB Output is correct
2 Correct 38 ms 9332 KB Output is correct
3 Correct 34 ms 9216 KB Output is correct
4 Correct 102 ms 36984 KB Output is correct
5 Correct 80 ms 37744 KB Output is correct
6 Correct 170 ms 36984 KB Output is correct
7 Correct 36 ms 9336 KB Output is correct
8 Correct 121 ms 37112 KB Output is correct
9 Correct 93 ms 37744 KB Output is correct
10 Correct 116 ms 37748 KB Output is correct
11 Correct 104 ms 23028 KB Output is correct
12 Correct 107 ms 30448 KB Output is correct
13 Correct 104 ms 23288 KB Output is correct
14 Correct 174 ms 37008 KB Output is correct
15 Correct 169 ms 36984 KB Output is correct
16 Correct 8 ms 7424 KB Output is correct
17 Correct 9 ms 7424 KB Output is correct
18 Correct 8 ms 7424 KB Output is correct
19 Correct 8 ms 7424 KB Output is correct
20 Correct 9 ms 7424 KB Output is correct
21 Correct 8 ms 7424 KB Output is correct
22 Correct 8 ms 7424 KB Output is correct
23 Correct 8 ms 7424 KB Output is correct
24 Correct 9 ms 7424 KB Output is correct
25 Correct 9 ms 7424 KB Output is correct