oj.uz

Submission #473377

# Submission time Handle Problem Language Result Execution time Memory
473377 2021-09-15T12:55:53 Z elgamalsalman Paths (BOI18_paths) C++14
100 / 100
 511 ms 109732 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

ll dp[350050][32];
int n, m, k, colours[350050];
vvi adj;

ll dfs(int u, int mask) {
  if (dp[u][mask] != -1) return dp[u][mask];
  //cerr << "// dfs(" << u << ", " << mask << ")\n";

  mask |= (1 << colours[u]);
  ll pathsCount = 0;
  for (int v : adj[u]) {
    if ((1 << colours[v]) & mask) continue;
    pathsCount += 1 + dfs(v, mask);
  }
  mask ^= (1 << colours[u]);

  dp[u][mask] = pathsCount;
  return dp[u][mask];
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  adj.assign(n + 20, vi());
  for (int i = 0; i < n; i++) {
    cin >> colours[i];
    colours[i]--;
  }

  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  memset(dp, -1, sizeof dp);
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    ans += dfs(i, 0);
  }

  cout << ans << '\n';
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 87936 KB Output is correct
2 Correct 42 ms 87872 KB Output is correct
3 Correct 41 ms 87876 KB Output is correct
4 Correct 39 ms 87940 KB Output is correct
5 Correct 39 ms 87888 KB Output is correct
6 Correct 39 ms 87876 KB Output is correct
7 Correct 40 ms 87872 KB Output is correct
8 Correct 40 ms 87940 KB Output is correct
9 Correct 41 ms 87924 KB Output is correct
10 Correct 39 ms 87916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 91720 KB Output is correct
2 Correct 110 ms 91492 KB Output is correct
3 Correct 419 ms 108296 KB Output is correct
4 Correct 173 ms 96488 KB Output is correct
5 Correct 146 ms 96584 KB Output is correct
6 Correct 309 ms 104700 KB Output is correct
7 Correct 404 ms 108944 KB Output is correct
8 Correct 409 ms 109732 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 87936 KB Output is correct
2 Correct 42 ms 87872 KB Output is correct
3 Correct 41 ms 87876 KB Output is correct
4 Correct 39 ms 87940 KB Output is correct
5 Correct 39 ms 87888 KB Output is correct
6 Correct 39 ms 87876 KB Output is correct
7 Correct 40 ms 87872 KB Output is correct
8 Correct 40 ms 87940 KB Output is correct
9 Correct 41 ms 87924 KB Output is correct
10 Correct 39 ms 87916 KB Output is correct
11 Correct 138 ms 91720 KB Output is correct
12 Correct 110 ms 91492 KB Output is correct
13 Correct 419 ms 108296 KB Output is correct
14 Correct 173 ms 96488 KB Output is correct
15 Correct 146 ms 96584 KB Output is correct
16 Correct 309 ms 104700 KB Output is correct
17 Correct 404 ms 108944 KB Output is correct
18 Correct 409 ms 109732 KB Output is correct
19 Correct 126 ms 94484 KB Output is correct
20 Correct 113 ms 93912 KB Output is correct
21 Correct 435 ms 108996 KB Output is correct
22 Correct 177 ms 96580 KB Output is correct
23 Correct 174 ms 96708 KB Output is correct
24 Correct 318 ms 104632 KB Output is correct
25 Correct 397 ms 108948 KB Output is correct
26 Correct 383 ms 109664 KB Output is correct
27 Correct 124 ms 93844 KB Output is correct
28 Correct 151 ms 95556 KB Output is correct
29 Correct 456 ms 108936 KB Output is correct
30 Correct 367 ms 101944 KB Output is correct
31 Correct 422 ms 101952 KB Output is correct
32 Correct 511 ms 109008 KB Output is correct
33 Correct 48 ms 87876 KB Output is correct
34 Correct 46 ms 87948 KB Output is correct
35 Correct 44 ms 87876 KB Output is correct
36 Correct 39 ms 87940 KB Output is correct
37 Correct 39 ms 87884 KB Output is correct
38 Correct 38 ms 88032 KB Output is correct
39 Correct 41 ms 88000 KB Output is correct
40 Correct 38 ms 87908 KB Output is correct
41 Correct 40 ms 87868 KB Output is correct
42 Correct 49 ms 87908 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 87876 KB Output is correct
2 Correct 75 ms 89116 KB Output is correct
3 Correct 62 ms 89744 KB Output is correct
4 Correct 117 ms 94864 KB Output is correct
5 Correct 102 ms 95708 KB Output is correct
6 Correct 162 ms 94820 KB Output is correct
7 Correct 66 ms 89740 KB Output is correct
8 Correct 144 ms 94808 KB Output is correct
9 Correct 108 ms 95604 KB Output is correct
10 Correct 131 ms 95380 KB Output is correct
11 Correct 134 ms 92224 KB Output is correct
12 Correct 113 ms 94100 KB Output is correct
13 Correct 138 ms 92520 KB Output is correct
14 Correct 157 ms 94788 KB Output is correct
15 Correct 126 ms 94912 KB Output is correct
16 Correct 41 ms 87952 KB Output is correct
17 Correct 45 ms 87876 KB Output is correct
18 Correct 39 ms 88004 KB Output is correct
19 Correct 44 ms 87984 KB Output is correct
20 Correct 40 ms 87884 KB Output is correct
21 Correct 38 ms 87936 KB Output is correct
22 Correct 38 ms 87984 KB Output is correct
23 Correct 37 ms 87876 KB Output is correct
24 Correct 39 ms 88000 KB Output is correct
25 Correct 39 ms 87924 KB Output is correct