Submission #283415

#	Time	Username	Problem	Language	Result	Execution time	Memory
283415		AlexLuchianov	Paths (BOI18_paths)	C++14	100 / 100	1129 ms	97400 KiB

paths

#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 300000;
int const sigma = 5;
int v[1 + nmax];
ll dp[1 + nmax][1 << sigma];
std::vector<int> g[1 + nmax];

int main() {
  int n, m, k;
  std::cin >> n >> m >> k;
  for(int i = 1;i <= n; i++) {
    std::cin >> v[i];
    v[i]--;
  }
  
  for(int i = 1;i <= m; i++) {
    int x, y;
    std::cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  ll result = 0;
  for(int mask = 1; mask < (1 << sigma); mask++) {
    for(int i = 1; i <= n; i++) {
      if(0 < ((1 << v[i]) & mask)) {
        if(0 < ((1 << v[i]) ^ mask)) {
          for(int h = 0; h < g[i].size(); h++) {
            int to = g[i][h];
            dp[i][mask] += dp[to][mask ^ (1 << v[i])];
          }
        } else
          dp[i][mask] = 1;
      }
      result += dp[i][mask];
    }
  }
  std::cout << result - n;
  return 0;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:35:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |           for(int h = 0; h < g[i].size(); h++) {
      |                          ~~^~~~~~~~~~~~~

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