QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#880815#4000. Dynamic ReachabilityliuruibinRE 0ms0kbC++144.7kb2025-02-03 21:08:122025-02-03 21:08:13

Judging History

This is the latest submission verdict.

  • [2025-02-03 21:08:13]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-03 21:08:12]
  • Submitted

answer

#include <bits/stdc++.h>
#define N 100011
using namespace std;
int n, m, q, U[N], V[N];
const int B = 180;
bitset<2 * B> to[2 * B], nto[2 * B];
vector<int> G[N], E[N];
int cmd[N][5], blk[N], bl[N], br[N], id[N];
bitset<2 * B> mset[N];
int dfn[N], low[N], clk, stk[N], nscc, scc[N];
bool vis[N];
void tarjan(int u)
{ //printf("tarjan(%d)\n",u);
    dfn[u] = low[u] = ++clk;
    vis[u] = 1;
    stk[++stk[0]] = u;
    for (int v : G[u])
    {
        if (!dfn[v])
            tarjan(v), low[u] = min(low[u], low[v]);
        else if (vis[v])
            low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        ++nscc;
        scc[u] = nscc;
        vis[u] = 0;
        while (stk[stk[0]] != u)
            scc[stk[stk[0]]] = nscc, vis[stk[stk[0]]] = 0, --stk[0];
        --stk[0];
    }
}
int Q[N], ql, qr;
bitset<2 * B> ok;
vector<int> vb, ve;
void bfs(int u)
{ //printf("--------------------bfs(%d)\n",u);
    ql = qr = 0;
    Q[qr++] = u;
    ok.reset();
    ok[u] = 1;
    while (ql ^ qr)
    {
        int p = Q[ql++]; //printf("p:%d\n",p);
        bitset<2 *B> nw = nto[p] ^ ok;
        // printf("nw:");for(int i=0;i<n;++i)printf("%d",(int)nw[i]);putchar(10);
        int id;
        while ((id = nw._Find_first()) < vb.size())
            ok[id] = 1, Q[qr++] = id, nw[id] = 0;
    }
}
bool cur[N], ine[N];
int main()
{
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        U[i] = u;
        V[i] = v;
        G[u].push_back(v);
    }
    for (int i = 1; i <= q; ++i)
    {
        int a, b, c;
        scanf("%d%d", &a, &b);
        if (a == 1)
        {
            cmd[i][0] = a, cmd[i][1] = U[b], cmd[i][2] = V[b], cmd[i][4] = b;
        }
        else
            cmd[i][0] = a, cmd[i][1] = b, scanf("%d", cmd[i] + 2);
    }
    for (int i = 1; i <= q; ++i)
        blk[i] = (i - 1) / B + 1;
    for (int i = 1; i <= blk[q]; ++i)
        bl[i] = (i - 1) * B + 1, br[i] = min(i * B, q);
    for (int i = 1; i <= m; ++i)
        cur[i] = 1;
    for (int $ = 1; $ <= (q - 1) / B + 1; ++$)
    { //printf("=============================================[%d,%d]\n",bl[$],br[$]);
        vb.clear();
        ve.clear();
        for (int i = 1; i <= m; ++i)
            ine[i] = 0;
        for (int i = 1; i <= n; ++i)
            id[i] = -1;
        for (int j = bl[$]; j <= br[$]; ++j)
        {
            if (!~id[cmd[j][1]])
                vb.push_back(cmd[j][1]), id[cmd[j][1]] = vb.size() - 1;
            if (!~id[cmd[j][2]])
                vb.push_back(cmd[j][2]), id[cmd[j][2]] = vb.size() - 1;
            if (cmd[j][0] == 1 && !ine[cmd[j][4]])
                ve.push_back(cmd[j][4]), ine[cmd[j][4]] = 1;
        }
        // printf("b:");for(int x:vb)printf("%d ",x);putchar(10);
        // printf("e:");for(int e:ve)printf("%d ",e);putchar(10);
        for (int u = 1; u <= n; ++u)
            G[u].clear();
        for (int i = 1; i <= m; ++i)
            if (cur[i] && !ine[i])
                G[U[i]].push_back(V[i]);
        for (int i = 1; i <= n; ++i)
            dfn[i] = 0;
        clk = nscc = stk[0] = 0;
        for (int i = 1; i <= n; ++i)
            if (!dfn[i])
                tarjan(i);
        // printf("scc:");for(int i=1;i<=n;++i)printf("%d ",scc[i]);putchar(10);
        for (int i = 1; i <= nscc; ++i)
            E[i].clear();
        for (int i = 1; i <= m; ++i)
            if (cur[i] && !ine[i] && scc[U[i]] != scc[V[i]])
                E[scc[U[i]]].push_back(scc[V[i]]);
        for (int i = 1; i <= nscc; ++i)
            mset[i].reset();
        for (int i = 0; i < vb.size(); ++i)
            mset[scc[vb[i]]][i] = 1;
        for (int i = 1; i <= nscc; ++i)
        {
            for (int v : E[i])
                mset[i] |= mset[v];
        }
        for (int i = 0; i < vb.size(); ++i)
        {
            for (int j = 0; j < vb.size(); ++j)
                to[i][j] = mset[scc[vb[i]]][j];
        }
        // printf("to:\n");
        // for(int i=0;i<vb.size();++i)
        // {
        // 	for(int j=0;j<vb.size();++j)printf("%d ",(int)to[i][j]);putchar(10);
        // }
        for (int i = bl[$]; i <= br[$]; ++i)
        {
            if (cmd[i][0] == 1)
                cur[cmd[i][4]] ^= 1;
            else
            {
                for (int u = 0; u < vb.size(); ++u)
                    nto[u] = to[u];
                for (int e : ve)
                    if (cur[e])
                        nto[id[U[e]]][id[V[e]]] = 1;
                bfs(id[cmd[i][1]]);
                printf(ok[id[cmd[i][2]]] ? "YES\n" : "NO\n");
            }
        }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

5 6 7
1 2
1 3
2 4
3 4
3 5
4 5
2 1 5
2 2 3
1 3
1 4
2 1 4
1 3
2 1 5

output:


result: