ABC287Ex Directed Graph and Query

传送门

思路

用 bitset 优化 Floyd，我们可以通过 \(O(\frac{n^3}{\omega})\) 的时间判断 \(i,~j\) 两点间是否联通。

因此，我们可以从小到大加入“中转点”，每加入一个，就将所有询问判断一遍。

总复杂度为 \(O(\frac{n^3}{\omega}+nq)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define max(x...) max({x})
#define min(x...) min({x})
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
inline int rd()
{
    int sign = 1, re = 0; char c = getchar();
    while(!isdigit(c)){if(c == '-') sign = -1; c = getchar();}
    while(isdigit(c)){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, m, q, s[10005], t[10005];
bitset<2005> r[2005];
int ans[10005];
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = rd(), m = rd();
    FOR(i, 1, m)
    {
        int u = rd(), v = rd();
        r[u][v] = 1;
    }
    q = rd();
    FOR(i, 1, q) s[i] = rd(), t[i] = rd(), ans[i] = -1;
    FOR(i, 1, n)
    {
        FOR(j, 1, n) if(r[j][i]) r[j] |= r[i];
        FOR(j, 1, q) if(r[s[j]][t[j]] && ans[j] == -1) ans[j] = i;
    }
    FOR(i, 1, q)
        if(~ans[i]) printf("%d\n", max(ans[i], s[i], t[i]));
        else puts("-1");
    return 0;
}