Codeforces Round #545 C. Museums Tour

https://codeforces.com/contest/1137/problem/C

We do not need to use GCD or something. We prepare the graph with N×D vertices and do SCC on it. Then, we can do dynamic programming on the contracted graph. The total time complexity is O(ND), but the hidden constant is large.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>

using namespace std;

struct strong {
  int N, K;
  vector<vector<int>> G, RG;
  vector<int> C;
  vector<bool> used;
  vector<int> post;
  vector<pair<int, int>> E;

  strong(int n) : N(n), K(0), G(n), RG(n), C(n, -1), used(n) {}

  void add(int u, int v) {
    G[u].push_back(v);
    RG[v].push_back(u);
  }

  void build() {
    for (int i = 0; i < N; i++) {
      dfs(i);
    }
    reverse(post.begin(), post.end());
    for (int i : post) {
      if (C[i] == -1) {
        dfs2(i, K++);
      }
    }
    for (int i = 0; i < N; i++) {
      for (int k : G[i]) {
        if (C[i] != C[k]) {
          E.emplace_back(C[i], C[k]);
        }
      }
    }
    sort(E.begin(), E.end());
  }

  void dfs(int u) {
    if (used[u]) return;
    used[u] = true;
    for (int v : G[u]) {
      dfs(v);
    }
    post.push_back(u);
  }

  void dfs2(int u, int k) {
    if (C[u] != -1) return;
    C[u] = k;
    for (int v : RG[u]) {
      dfs2(v, k);
    }
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N, M, D;
  cin >> N >> M >> D;
  strong scc(N * D);
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    u--; v--;
    for (int j = 0; j < D; j++) {
      scc.add(u * D + j, v * D + (j + 1) % D);
    }
  }
  vector<string> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }
  scc.build();
  vector<int> dp(scc.K, -1e9);
  vector<int> cnt(scc.K);
  for (int i = 0; i < N; i++) {
    set<int> st;
    for (int j = 0; j < D; j++) {
      if (S[i][j] == '1') {
        st.insert(scc.C[i * D + j]);
      }
    }
    for (int x : st) {
      cnt[x]++;
    }
  }
  dp[scc.C[0]] = 0;
  for (auto e : scc.E) {
    dp[e.second] = max(dp[e.second], dp[e.first] + cnt[e.first]);
  }
  int ans = 0;
  for (int i = 0; i < scc.K; i++) {
    ans = max(ans, dp[i] + cnt[i]);
  }
  cout << ans << '\n';
}