提出 #38449716

---

ソースコード 拡げる

#include <iostream>
#include <queue>
#include <bitset>
#include <vector>
#define N 2100
#define Q 11000
using namespace std;
int n, m, q, s[Q], t[Q], ans[Q];
bitset<N> bt[N];
vector<int> v[N], rev[N];
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int a, b;
    cin >> a >> b;
    v[a].push_back(b);
    rev[b].push_back(a);
  }
  cin >> q;
  for (int i = 1; i <= q; i++)
    cin >> s[i] >> t[i];
  memset(ans, -1, sizeof(ans));
  for (int i = 1; i <= n; i++) {
    bt[i][i] = 1;
    for (auto to : v[i]) {
      if (to < i)
        bt[i] |= bt[to];
    }
    bitset<N> tmp;
    for (auto to : rev[i]) {
      if (to < i)
        tmp[to] = 1;
    }
    for (int j = 1; j < i; j++) {
      if ((bt[j] & tmp).count())
        bt[j] |= bt[i];
    }
    for (int j = 1; j <= q; j++) {
      if (bt[s[j]][t[j]] && ans[j] == -1) {
        ans[j] = i;
      }
    }
  }
  for (int i = 1; i <= q; i++)
    cout << ans[i] << '\n';
  return 0;
}

提出情報

ジャッジ結果