Submission #789520

#	Time	Username	Problem	Language	Result	Execution time	Memory
789520		Trisanu_Das	Paths (BOI18_paths)	C++17	0 / 100	115 ms	17680 KiB

paths

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30