Submission #28747761

---

Source Code Expand

#include <immintrin.h>

#include <algorithm>
#include <bitset>
#include <cstring>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

#define rep(i, n) for (int i = 0; i < n; i++)

using bs = bitset<128>;

void mul(bs* A, bs* B, bs* C, int n) {
  rep(i, n) C[i].reset();
  for (int i = 0; i < n; i += 8) {
    for (int j = 0; j < n; j++) {
#define add(x, y) \
  if (A[i + x].test(j + y)) C[i + x] |= B[j + y];
      add(0, 0);
      add(1, 0);
      add(2, 0);
      add(3, 0);
      add(4, 0);
      add(5, 0);
      add(6, 0);
      add(7, 0);
    }
  }
}

bs a[105];
bs b[105];
bs c[105];
bs d[105];

// pow(a, L) を c に格納
void mat_pow(int L, int n) {
  memcpy(b, a, sizeof(a));
  memset(c, 0, sizeof(c));
  rep(i, n) c[i][i] = 1;
  while (L) {
    if (L & 1) {
      mul(b, c, d, n);
      memcpy(c, d, sizeof(c));
    }
    mul(b, b, d, n);
    memcpy(b, d, sizeof(d));
    L >>= 1;
  }
}

int inf = 1001001001;

int main() {
  int N, T, L;
  cin >> N >> T >> L;

  vector<pair<int, int>> es;
  for (int i = 1, u, v; i <= T; i++) {
    cin >> u >> v;
    --u, --v;
    es.emplace_back(u, v);
  }

  vector<int> ng(N, -1);
  vector<int> ok(N, T);

  while (true) {
    vector<pair<int, int>> qs;
    rep(i, N) {
      if (ng[i] + 1 < ok[i]) {
        int med = (ng[i] + ok[i]) / 2;
        qs.emplace_back(med, i);
      }
    }
    if (qs.empty()) break;
    sort(begin(qs), end(qs));
    reverse(begin(qs), end(qs));

    memset(a, 0, sizeof(a));

    rep(i, T) {
      if (qs.empty()) break;
      a[es[i].first][es[i].second] = 1;
      if (qs.back().first == i) {
        mat_pow(L, N);
        while (qs.size() and qs.back().first == i) {
          int j = qs.back().second;
          qs.pop_back();
          if (c[0][j] == 1) {
            ok[j] = i;
          } else {
            ng[j] = i;
          }
        }
      }
    }
  }

  for (auto& x : ok)
    if (++x == T + 1) x = -1;
  rep(i, N) cout << ok[i] << " \n"[i == N - 1];
}

Submission Info

Judge Result