Submission #28747672

---

Source Code Expand

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

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

using bs = bitset<128>;
using mat = array<bs, 100>;

mat mat_mul(mat A, mat B, int n) {
  mat C;
  rep(i, n) C[i].reset();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (A[i].test(j)) C[i] |= B[j];
    }
  }
  return C;
}

mat mat_pow(mat a, int L, int n) {
  mat c;
  rep(i, n) {
    c[i].reset();
    c[i][i] = true;
  }
  while (L) {
    if (L & 1) c = mat_mul(a, c, n);
    L >>= 1;
    if (L) a = mat_mul(a, a, n);
  }
  return c;
}

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));

    mat a;
    for (int i = 0; i < N; i++) a[i].reset();

    rep(i, T) {
      if (qs.empty()) break;
      a[es[i].first][es[i].second] = 1;
      if (qs.back().first == i) {
        mat c = mat_pow(a, 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