QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#390258 | #5704. Joker | Nelofus | 0 | 86ms | 15652kb | C++20 | 2.7kb | 2024-04-15 10:55:32 | 2024-04-15 10:55:33 |
Judging History
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%