oj.uz

Submission #807572

# Submission time Handle Problem Language Result Execution time Memory
807572 2023-08-04T19:33:58 Z dong_liu Paths (BOI18_paths) C++17
100 / 100
 229 ms 46272 KB 
#include <iostream>
#include <vector>
using namespace std;

#define ll long long

inline int p2(const int& b) { return 1 << b; }

const int N = 3e5, K = 5;

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n, m, k;
  cin >> n >> m >> k;
  static int c[N];
  for (int i = 0; i < n; i++) cin >> c[i], c[i]--;
  static vector<int> g[N];
  static ll f[1 << K][N];
  for (int h = 0; h < m; h++) {
    int i, j;
    cin >> i >> j, i--, j--;
    if (c[i] != c[j]) {
      g[i].push_back(j), g[j].push_back(i);
      f[p2(c[i]) | p2(c[j])][i] += 1, f[p2(c[i]) | p2(c[j])][j] += 1;
    }
  }
  ll ans = 0;
  for (int b = 0; b < 1 << k; b++)
    for (int i = 0; i < n; i++)
      if (f[b][i]) {
        ans += f[b][i];
        for (int j : g[i])
          if (!(b & p2(c[j]))) f[b | p2(c[j])][j] += f[b][i];
      }
  cout << ans << '\n';
  return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7368 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 3 ms 7380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 13180 KB Output is correct
2 Correct 61 ms 11596 KB Output is correct
3 Correct 157 ms 29436 KB Output is correct
4 Correct 64 ms 13480 KB Output is correct
5 Correct 45 ms 10800 KB Output is correct
6 Correct 110 ms 24192 KB Output is correct
7 Correct 209 ms 29412 KB Output is correct
8 Correct 209 ms 30216 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7368 KB Output is correct
2 Correct 5 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7368 KB Output is correct
7 Correct 4 ms 7376 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 3 ms 7380 KB Output is correct
10 Correct 3 ms 7380 KB Output is correct
11 Correct 58 ms 13180 KB Output is correct
12 Correct 61 ms 11596 KB Output is correct
13 Correct 157 ms 29436 KB Output is correct
14 Correct 64 ms 13480 KB Output is correct
15 Correct 45 ms 10800 KB Output is correct
16 Correct 110 ms 24192 KB Output is correct
17 Correct 209 ms 29412 KB Output is correct
18 Correct 209 ms 30216 KB Output is correct
19 Correct 58 ms 13236 KB Output is correct
20 Correct 44 ms 11648 KB Output is correct
21 Correct 165 ms 29300 KB Output is correct
22 Correct 61 ms 13476 KB Output is correct
23 Correct 56 ms 10828 KB Output is correct
24 Correct 118 ms 24236 KB Output is correct
25 Correct 166 ms 29296 KB Output is correct
26 Correct 159 ms 30220 KB Output is correct
27 Correct 64 ms 13328 KB Output is correct
28 Correct 72 ms 13768 KB Output is correct
29 Correct 229 ms 46260 KB Output is correct
30 Correct 130 ms 29964 KB Output is correct
31 Correct 135 ms 28996 KB Output is correct
32 Correct 228 ms 46272 KB Output is correct
33 Correct 4 ms 7380 KB Output is correct
34 Correct 3 ms 7380 KB Output is correct
35 Correct 4 ms 7380 KB Output is correct
36 Correct 3 ms 7380 KB Output is correct
37 Correct 4 ms 7380 KB Output is correct
38 Correct 3 ms 7380 KB Output is correct
39 Correct 4 ms 7380 KB Output is correct
40 Correct 5 ms 7380 KB Output is correct
41 Correct 3 ms 7372 KB Output is correct
42 Correct 3 ms 7380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7404 KB Output is correct
2 Correct 33 ms 9428 KB Output is correct
3 Correct 17 ms 9168 KB Output is correct
4 Correct 44 ms 14572 KB Output is correct
5 Correct 36 ms 13796 KB Output is correct
6 Correct 78 ms 32076 KB Output is correct
7 Correct 19 ms 9312 KB Output is correct
8 Correct 58 ms 20264 KB Output is correct
9 Correct 50 ms 16512 KB Output is correct
10 Correct 38 ms 17288 KB Output is correct
11 Correct 52 ms 20768 KB Output is correct
12 Correct 38 ms 17172 KB Output is correct
13 Correct 42 ms 18128 KB Output is correct
14 Correct 100 ms 32192 KB Output is correct
15 Correct 72 ms 32304 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 5 ms 7496 KB Output is correct
18 Correct 4 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 5 ms 7380 KB Output is correct
22 Correct 5 ms 7380 KB Output is correct
23 Correct 5 ms 7492 KB Output is correct
24 Correct 3 ms 7380 KB Output is correct
25 Correct 3 ms 7372 KB Output is correct