提出 #28779195

---

ソースコード 拡げる

#include <immintrin.h>

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

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

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

using bs = bitset<128>;

constexpr int MAX = 30;
int N, T, L;
int u[10000], v[10000];
bs a[MAX][100];
bs at[MAX][100];

// t 番目の (i, j) を更新
void dfs(int t, int i, int j) {
  // cerr<<"dfs:"<<t<<" "<<i<<" "<<j<<endl;
  if (a[t][i].test(j)) return;
  a[t][i].set(j), at[t][j].set(i);
  if (t == MAX - 1) return;
  bs s1 = a[t][j] & ~a[t + 1][i];
  for (int k = s1._Find_first(); k < N; k = s1._Find_next(k)) {
    dfs(t + 1, i, k);
  }
  bs s2 = at[t][i] & ~at[t + 1][j];
  for (int h = s2._Find_first(); h < N; h = s2._Find_next(h)) {
    dfs(t + 1, h, j);
  }
}

bs v1, v2;
// v1 に答えを set
void get() {
  v1.reset();
  v1.set(0);
  for (int b = 0; b < MAX; b += 2) {
    if (L & (1 << b)) {
      rep(i, N) v2[i] = (at[b + 0][i] & v1).count() > 0;
    } else {
      v2 = v1;
    }
    if (L & (1 << (b + 1))) {
      rep(i, N) v1[i] = (at[b + 1][i] & v2).count() > 0;
    } else {
      v1 = v2;
    }
  }
}

int ng[100], ok[100];

int main() {
  cin >> N >> T >> L;
  rep(i, T) {
    cin >> u[i] >> v[i];
    --u[i], --v[i];
  }

  rep(i, N) ng[i] = -1, ok[i] = 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));
    memset(at, 0, sizeof(a));

    rep(t, T) {
      if (qs.empty()) break;
      dfs(0, u[t], v[t]);
      if (qs.back().first == t) {
        get();
        while (qs.size() and qs.back().first == t) {
          int j = qs.back().second;
          qs.pop_back();
          if (v1.test(j)) {
            ok[j] = t;
          } else {
            ng[j] = t;
          }
        }
      }
    }
  }

  rep(i, N) {
    int x = ok[i] == T ? -1 : ok[i] + 1;
    cout << x << " \n"[i == N - 1];
  }
}

提出情報

ジャッジ結果