QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#806755 | #4000. Dynamic Reachability | user10086 | RE | 6290ms | 33248kb | C++23 | 3.8kb | 2024-12-09 14:51:38 | 2024-12-09 14:51:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, B = 320, K = N / B + 10;
struct Q1
{
int t, k;
};
struct Q2
{
int id, t, u, v;
};
int n, m, q, fl[N], used[N], ans[N], idx[N], vis[N];
array<int, 2> el[N];
vector<Q2> q2[K];
int sz[K];
vector<Q1> q1[K];
vector<int> g[N], g2[N], g3[N];
bitset<B << 1> from[N], to[N];
int tick, sccn, dfn[N], low[N], col[N], instk[N];
vector<int> stk;
void tarjan(int x)
{
tick++, dfn[x] = low[x] = tick;
stk.push_back(x), instk[x] = true;
for (int y : g[x])
{
if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
else if (instk[y]) low[x] = min(low[x], dfn[y]);
}
if (low[x] == dfn[x])
{
sccn++;
int u;
do
{
u = stk.back(); stk.pop_back(); instk[u] = false;
col[u] = sccn;
to[sccn].set(idx[u]), from[sccn].set(idx[u]);
} while (u != x);
}
}
int ind[N];
void pre()
{
queue<int> q;
vector<int> topo;
for (int i = 1; i <= sccn; i++)
if (!ind[i]) q.push(i);
while (!q.empty())
{
int k = q.front(); q.pop();
topo.push_back(k);
for (int x : g2[k])
{
ind[x]--;
if (!ind[x]) q.push(x);
}
}
for (int x : topo)
for (int y : g3[x])
from[y] |= from[x];
reverse(topo.begin(), topo.end());
for (int x : topo)
for (int y : g2[x])
to[x] |= to[y];
}
bool dfs(int x)
{
if (x == n + 2) return true;
vis[x] = true;
for (int y : g2[x])
if (!vis[y])
if (dfs(y)) return true;
return false;
}
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) cin >> el[i][0] >> el[i][1], fl[i] = true;
int qn = ceil(sqrt(q)), k = q / B, cnt2 = 0;
for (int i = 1; i <= q; i++)
{
int op, k, u, v; cin >> op;
if (op == 1) cin >> k, q1[i / B].push_back({i, k});
if (op == 2) cin >> u >> v, cnt2++, q2[i / B].push_back({cnt2, i, u, v});
}
for (int i = 0; i <= k; i++)
{
// cerr << i << ' ' << k << ' ' << clock() << endl;
for (int i = 1; i <= n; i++) g[i].clear(), from[i].reset(), to[i].reset(), idx[i] = 0, dfn[i] = 0, assert(!ind[i]); tick = sccn = 0;
for (Q1 q : q1[i]) used[q.k] = true;
for (int i = 1; i <= m; i++)
if (fl[i] && !used[i]) g[el[i][0]].push_back(el[i][1]);
for (Q1 q : q1[i]) used[q.k] = false;
set<int> qp;
for (Q2 q : q2[i]) qp.insert(q.u), qp.insert(q.v);
int cur = 0;
for (int x : qp) cur++, idx[x] = cur;
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
for (int i = 1; i <= sccn; i++) g2[i].clear(), g3[i].clear();
for (int i = 1; i <= n; i++)
for (int j : g[i])
if (col[i] != col[j]) g2[col[i]].push_back(col[j]), g3[col[j]].push_back(col[i]), ind[col[j]]++;
pre();
// for (int i = 1; i <= n; i++)
// for (int j = 1; j <= n; j++)
// if (to[i][j]) printf("to[%d][%d]\n", i, j);
//
// printf("***%d\n", i);
// for (int i = 1; i <= n; i++) printf("idx[%d] = %d\n", i, idx[i]);
for (int i = 1; i <= n + 2; i++) g2[i].clear();
for (Q2 q : q2[i])
{
int t = q.t, u = q.u, v = q.v;
if (to[col[u]][idx[v]])
{
ans[q.id] = 1;
continue;
}
vector<int> edit;
map<array<int, 2>, int> s;
for (Q1 q : q1[i])
{
if (q.t > t) break;
auto e = el[q.k];
if (s.count(e)) s[e] ^= (q.t < t);
else s[e] = fl[q.k] ^ (q.t < t);
}
for (auto p : s)
{
if (!p.second) continue;
int x = p.first[0], y = p.first[1];
if (from[col[y]][idx[u]] || to[col[x]][idx[v]]) continue;
if (from[col[x]][idx[u]]) x = n + 1;
if (to[col[y]][idx[v]]) y = n + 2;
g2[x].push_back(y), edit.push_back(x);
}
ans[q.id] = dfs(n + 1);
for (int x : edit) g2[x].clear();
}
for (Q1 q : q1[i]) fl[q.k] ^= 1;
}
for (int i = 1; i <= cnt2; i++) cout << (ans[i] ? "YES" : "NO") << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 11744kb
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:
YES NO NO YES
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 6290ms
memory: 32788kb
input:
50000 100000 100000 36671 44121 25592 44321 13226 46463 13060 25694 14021 20087 22881 38333 34655 47774 22868 26462 31154 48710 27491 32365 5874 47497 17622 28600 1886 14193 22315 23656 14973 22704 1335 25384 22612 34915 2852 48213 23334 25519 24342 28784 6238 36125 14598 39494 33069 34250 2123 3059...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 50000 lines
Test #3:
score: 0
Accepted
time: 6155ms
memory: 33248kb
input:
50000 100000 100000 27059 36120 32335 41190 9436 29046 36520 44281 25005 39115 37096 43321 11891 38873 10439 31878 19154 25918 26756 44170 9594 16092 9920 23747 17107 35055 31401 35308 17102 35604 18635 26767 27925 29726 7012 14266 973 21483 622 41029 25685 31856 36951 46699 18103 46885 9911 18465 2...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 50000 lines
Test #4:
score: -100
Runtime Error
input:
50000 100000 100000 7 14 14 21 21 28 28 35 35 42 42 49 49 56 56 63 63 70 70 77 77 84 84 91 91 98 98 105 105 112 112 119 119 126 126 133 133 140 140 147 147 154 154 161 161 168 168 175 175 182 182 189 189 196 196 203 203 210 210 217 217 224 224 231 231 238 238 245 245 252 252 259 259 266 266 273 273 ...