QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#384734	#4420. Range Reachability Query	Eray	AC ✓	2618ms	24676kb	C++14	1.6kb	2024-04-10 11:31:47	2024-04-10 11:31:47

Judging History

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

[2024-04-10 11:31:47]
评测

测评结果：AC
用时：2618ms
内存：24676kb

查看

[2024-04-10 11:31:47]
提交

answer

#include <bits/stdc++.h>

const int N = 5e4 + 5;
const int M = 1e5 + 5;
const int D = 1000;
const int MAXQ = 5e4 + 5;

int n, m, Q;
struct Edge { int to, nxt; } edge[M];
int head[N], ek;
void add_edge(int u, int v) { edge[ek] = (Edge){v, head[u]}, head[u] = ek++; }

std::bitset<D> bs[N], qe[M];
int st[MAXQ], ed[MAXQ], ql[MAXQ], qr[MAXQ];

int ind[N], indc[N];
void toposort() {
	for(int i = 1; i <= n; i++) ind[i] = indc[i];
	std::vector<int> vct;
	for(int i = 1; i <= n; i++) if(!ind[i]) vct.emplace_back(i);
	while(!vct.empty()) {
		int u = vct.back();
		vct.pop_back();
		for(int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			bs[v] |= bs[u] & qe[i];
			ind[v]--;
			if(!ind[v]) vct.emplace_back(v);
		}
	}
}

int main() {
	int T; scanf("%d", &T);
	while(T--) {
		ek = 1;
		scanf("%d%d%d", &n, &m, &Q);
		for(int i = 1; i <= n; i++) head[i] = 0, indc[i] = 0;
		for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); add_edge(u, v), indc[v]++; }
		for(int i = 1; i <= Q; i++) scanf("%d%d%d%d", &st[i], &ed[i], &ql[i], &qr[i]);
		for(int q = 1; q <= Q; q += D) {
			for(int i = 1; i <= n; i++) bs[i].reset();
			for(int i = 1; i <= m; i++) qe[i].reset();
			for(int i = q; i <= std::min(q + D - 1, Q); i++) bs[st[i]].set(i - q), qe[ql[i]].set(i - q), qe[qr[i] + 1].set(i - q);
			for(int i = 1; i <= m; i++) qe[i] ^= qe[i - 1];
			toposort();
			for(int i = q; i <= std::min(q + D - 1, Q); i++) puts(bs[ed[i]][i - q] ? "YES" : "NO");
		}
	}
	return 0;
} /*
1
5 6 5
1 2
1 3
3 4
2 4
2 5
3 5
3 5 1 5
3 5 1 6
1 4 1 6
1 4 2 3
1 4 4 5
*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2618ms

memory: 24676kb

input:

10
50000 100000 50000
42489 42490
40572 40573
33841 33842
18146 37295
31294 31295
9813 45992
25570 38939
24581 24582
13580 38328
35265 35266
11229 11230
28548 28549
25253 45063
9721 9722
31522 35509
4701 18080
8261 11199
35982 35983
26823 26824
44922 44923
19236 44157
41597 41598
22648 22649
39838 3...

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
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
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 500000 lines