oj.uz

Submission #789520

# Submission time Handle Problem Language Result Execution time Memory
789520 2023-07-21T13:05:29 Z Trisanu_Das Paths (BOI18_paths) C++17
0 / 100
 115 ms 17680 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, k, a[300005], dt[1 << 5][300005], ans, u, v;
vector<int> adj[300005];

signed main(){
  cin >> n >> m >> k;
  for(int i = 1; i < n + 1; i++) {cin >> a[i], a[i]--;}
  for(int i = 1; i < m + 1; i++){
    cin >> u >> v;
    adj[u].push_back(v); adj[v].push_back(u);
  }
  for(int m = 1; m < (1 << k); m++){
    for(int u = 1; u < n + 1; u++){
      int j = 1 << a[u];
      if(!(j & m)) continue;
      if(j == m) dt[m][u] = 1;
      for(auto v : adj[u]) dt[m][u] += dt[m - j][v];
      ans += dt[m][u];
    }
  }
  cout << ans << '\n';
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 115 ms 17680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 7508 KB Output isn't correct
2 Halted 0 ms 0 KB -