QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#806755#4000. Dynamic Reachabilityuser10086RE 6290ms33248kbC++233.8kb2024-12-09 14:51:382024-12-09 14:51:39

Judging History

你现在查看的是最新测评结果

  • [2024-12-09 14:51:39]
  • 评测
  • 测评结果:RE
  • 用时:6290ms
  • 内存:33248kb
  • [2024-12-09 14:51:38]
  • 提交

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 ...

output:


result: