Submission #789522

#	Time	Username	Problem	Language	Result	Execution time	Memory
789522		Trisanu_Das	Paths (BOI18_paths)	C++17	100 / 100	367 ms	59864 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 << '\n';
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30