제출 #1276464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276464		rtri	Paths (BOI18_paths)	C++20	100 / 100	738 ms	69664 KiB

paths

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

ll n, m, k;
vector<ll> colors;
vector<vector<ll>> adj;
vector<vector<ll>> ans;

int main() {
  cin >> n >> m >> k;

  colors.resize(n);
  for (ll i = 0; i < n; i++) {
    cin >> colors[i];
    colors[i]--;
  }

  adj.resize(n);
  for (ll i = 0; i < m; i++) {
    ll a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  ans.resize(n, vector<ll>((1 << k) + 1, 0));
  for (ll u = 0; u < n; u++)
    ans[u][1 << colors[u]] = 1;

  for (int i = 1; i <= k; i++) {
    for (ll u = 0; u < n; u++) {
      for (ll v : adj[u]) {
        for (int mask = 1; mask < (1 << k); mask++) {
          int me = 1 << colors[u];
          if (0 < (mask & me))
            continue;
          if (__builtin_popcountll(mask) != i)
            continue;
          ans[u][me | mask] += ans[v][mask];
        }
      }
    }
  }

  ll anssum = 0;
  for (ll u = 0; u < n; u++)
    for (int mask = 1; mask <= (1 << k); mask++) {
      if (__builtin_popcountll(mask) <= 1)
        continue;
      anssum += ans[u][mask];
    }

  cout << anssum << endl;

  return 0;
}

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