Submission #1143514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143514		LucaLucaM	Paths (BOI18_paths)	C++20	100 / 100	144 ms	52216 KiB

paths

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

const int NMAX = 3e5;

int a[NMAX + 1];
std::vector<int> g[NMAX + 1];

ll dp[1 << 5][NMAX + 1];

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m, k;
  std::cin >> n >> m >> k;

  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
    a[i]--;
  }

  while (m--) {
    int u, v;
    std::cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  for (int i = 1; i <= n; i++) {
    dp[1 << a[i]][i] = 1;
  }

  for (int mask = 0; mask < (1 << k); mask++) {
    for (int i = 1; i <= n; i++) {
      if (mask >> a[i] & 1) {
        for (const auto &j : g[i]) {
          dp[mask][i] += dp[mask ^ (1 << a[i])][j];
        }
      }
    }
  }

  ll answer = 0;

  for (int mask = 1; mask < (1 << k); mask++) {
    if ((mask & (mask - 1)) != 0) {
      for (int i = 1; i <= n; i++) {
        answer += dp[mask][i];
      }
    }
  }

  std::cout << answer;

  return 0;
}

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