QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#880815 | #4000. Dynamic Reachability | liuruibin | RE | 0ms | 0kb | C++14 | 4.7kb | 2025-02-03 21:08:12 | 2025-02-03 21:08:13 |
Judging History
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