QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390258#5704. JokerNelofus0 86ms15652kbC++202.7kb2024-04-15 10:55:322024-04-15 10:55:33

Judging History

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

  • [2024-04-15 10:55:33]
  • 评测
  • 测评结果:0
  • 用时:86ms
  • 内存:15652kb
  • [2024-04-15 10:55:32]
  • 提交

answer

/*
 * Copyright© 2024 Heratino & Nelofus. All rights reserved.
 * author: Heratino & Nelofus
 * Problem: 
 * Tag: 
 * Memory Limit: 
 * Time Limit: 
 * Source: 
 */

// Narcissus & どうか安寧な記憶を

#include <bits/stdc++.h>
using i64 = long long;

//{{{一等星
char buf[1 << 20], *P1 = buf, *P2 = buf;
inline char gc() {
	if (P1 == P2)
		P2 = (P1 = buf) + fread(buf, 1, 1 << 20, stdin);
	return P1 == P2 ? EOF : *P1++;
}

inline i64 read() {
	i64 s = 0, w = 1;
	char c = gc();
	while (!isdigit(c)) {
		if (c == '-')
		   w = -1;
		c = gc();
	}
	while (isdigit(c))
		s = (s << 3) + (s << 1) + (c ^ 48), c = gc();
	return s * w;
}
//}}}

constexpr int N = 2e5 + 10;
constexpr int M = 2 * N;

int n, m, q;
std::pair<int, int> edge[M];
struct queries {
	int l, r;
	int reach;
	int id;
	bool operator < (const queries &t) {
		return r < t.r;
	}
} Q[N];

std::stack<std::pair<int, int>, std::vector<std::pair<int, int>>> stk;
int fa[M], siz[M];
int find(int x) {return x == fa[x] ? x : find(fa[x]);}

bool undo() {
	if (stk.empty())
		return false;
	auto [u, x] = stk.top();
	siz[fa[u]] = x;
	fa[u] = u;
	stk.pop();
	return true;
}

bool merge(int u, int v) {
	int fu = find(u), fv = find(v);
	if (fu == fv)
		return false;
	if (siz[fu] > siz[fv])
		std::swap(fu, fv);
	stk.push(std::make_pair(fu, siz[fv]));
	fa[fu] = fv;
	siz[fv] += siz[fu];
	return true;
}

void divide(int l, int r, int ql, int qr) {
	int mid = l + r >> 1;
	int qmid = Q[mid].r;
	for (int i = std::min(qr, Q[mid].r); i >= ql; i--) {
		const auto &[u, v] = edge[i];
		merge(u + N, v), merge(v + N, u);
		if (find(u) != find(v))
			qmid = i;
		else
			break;
	}
	// 清空并查集
	while (undo());
	Q[mid].reach = qmid;
	if (l < mid)
		divide(l, mid - 1, ql, qmid);
	if (r > mid)
		divide(mid + 1, r, qmid, qr);
}

bool ans[N];
/* 无法忘却的记忆与苍蓝之梦 */
int main() {
#ifdef HeratinoNelofus
	freopen("input.txt", "r", stdin);
#endif
	for (int i = 1; i < M; i++)
		fa[i] = i, siz[i] = 1;

	n = read(), m = read(), q = read();
	for (int i = 1; i <= m; i++) {
		auto &[ll, lr] = edge[i];
		auto &[rl, rr] = edge[i + m];
		ll = read(), lr = read();
		rl = ll, rr = lr;
	}
	for (int i = 1; i <= q; i++) {
		auto &[l, r, rea, id] = Q[i];
		int tl = read(), tr = read();
		
		l = tr + 1;
		r = tl + m - 1;
		id = i;
	}
	std::sort(Q + 1, Q + 1 + q);
	divide(1, q, 1, 2 * m);
	for (int i = 1; i <= q; i++) {
		auto &[l, r, rea, id] = Q[i];
		// 最早的,不是奇环的点
		if (rea > l)
			ans[id] = true;
		else
			ans[id] = false;
	}
	for (int i = 1; i <= q; i++)
		if (ans[i])
			std::cout << "YES" << '\n';
		else
			std::cout << "NO" << '\n';
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 6
Accepted
time: 0ms
memory: 11432kb

input:

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

output:

NO
YES

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 10112kb

input:

2 1 1
1 2
1 1

output:

NO

result:

ok single line: 'NO'

Test #3:

score: -6
Wrong Answer
time: 2ms
memory: 11344kb

input:

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

output:

NO
YES
NO
YES
YES
YES

result:

wrong answer 1st lines differ - expected: 'YES', found: 'NO'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #55:

score: 0
Wrong Answer
time: 86ms
memory: 15652kb

input:

100000 199997 200000
79109 44896
79109 66117
66117 91800
91800 24387
24387 74514
48558 74514
48558 37561
37561 76920
79598 76920
79598 69196
69196 79004
49065 79004
70038 49065
15497 70038
15497 67507
25073 67507
25073 41762
41762 71848
71848 32073
32073 43754
72852 43754
41209 72852
68112 41209
629...

output:

NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
YES
NO
NO
NO
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
YES
NO
NO
YES
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
NO
NO
NO
YES
NO
NO
NO
NO
YES
...

result:

wrong answer 100001st lines differ - expected: 'YES', found: 'NO'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #2:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%