Submission #796243

#	Time	Username	Problem	Language	Result	Execution time	Memory
796243		tch1cherin	Paths (BOI18_paths)	C++17	100 / 100	274 ms	103044 KiB

paths

#include <bits/stdc++.h>
using namespace std;
 
const int MAX_N = 300005;
vector<int> G[MAX_N];
int A[MAX_N], cnt[MAX_N][5];
int64_t c[MAX_N][1 << 5];
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, K;
  cin >> N >> M >> K;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    A[i]--;
  }
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<int> pc(1 << K);
  for (int i = 0; i < (1 << K); i++) {
    pc[i] = __builtin_popcount(i);
  }
  for (int i = 0; i < N; i++) {
    for (int j : G[i]) {
      cnt[i][A[j]]++;
    }
  }
  int64_t ans = 0;
  vector<int64_t> len(5);
  for (int i = 0; i < N; i++) {
    c[i][0] = 1;
    for (int j : G[i]) {
      c[i][1 << A[j]]++; 
      for (int k = 0; k < K; k++) {
        if (A[j] != k) {
          c[i][(1 << A[j]) | (1 << k)] += cnt[j][k];
        } 
      } 
    }
    for (int msk1 = 0; msk1 < (1 << K); msk1++) {
      if ((msk1 >> A[i]) & 1) {
        continue;
      }
      for (int msk2 = 0; msk2 < (1 << K); msk2++) {
        if (((msk2 >> A[i]) & 1) || (msk1 & msk2)) {
          continue;
        }
        len[pc[msk1 | msk2]] += c[i][msk1] * c[i][msk2];
      }
    }
  }
  cout << len[1] / 2 + len[2] / 3 + len[3] / 2 + len[4] << "\n"; 
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:33:11: warning: unused variable 'ans' [-Wunused-variable]
   33 |   int64_t ans = 0;
      |           ^~~

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