Submission #185432

#	Time	Username	Problem	Language	Result	Execution time	Memory
185432		AlexPop28	Paths (BOI18_paths)	C++11	100 / 100	953 ms	108396 KiB

paths

#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<

using namespace std;

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

  int n, m, k; cin >> n >> m >> k;
  vector<int> col(n);
  vector<vector<long long>> dp(n, vector<long long>(1 << k));
  vector<vector<bool>> inq(n, vector<bool>(1 << k));
  vector<pair<int, int>> q;
  for (int i = 0; i < n; ++i) {
    cin >> col[i]; --col[i];
    q.emplace_back(i, 1 << col[i]);
    dp[i][1 << col[i]] = 1;
    inq[1][1 << col[i]] = true;
  }
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    int a, b; cin >> a >> b; --a, --b;
    adj[a].emplace_back(b);
    adj[b].emplace_back(a);
  }
  long long ans = 0LL;
  for (int it = 0; it < (int)q.size(); ++it) {
    int node, mask; tie(node, mask) = q[it];
    inq[node][mask] = false;
    ans += dp[node][mask];
    for (int &x : adj[node]) {
      if ((1 << col[x]) & mask) continue;
      int next = mask | (1 << col[x]);
      dp[x][next] += dp[node][mask];
      if (!inq[x][next]) {
        q.emplace_back(x, next);
        inq[x][next] = true;
      }
    }
  }
  cout << ans - n << endl;
}

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