QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#806609 | #9810. Obliviate, Then Reincarnate | lym | WA | 0ms | 3820kb | C++20 | 1.2kb | 2024-12-09 12:55:59 | 2024-12-09 12:56:00 |
Judging History
answer
#include<bits/stdc++.h>
using i64 = long long;
#define int i64
void solve() {
int n, m, q;
std::cin >> n >> m >> q;
std::vector<std::vector<int> > e(n);
for (int i = 1; i <= m; i ++) {
int u, d;
std::cin >> u >> d;
if (d == 0) continue;
int v = ((u + d) % n + n) % n;
u = (u % n + n) % n;
e[u].push_back(v);
}
// 0... n - 1
std::vector<int> f(n);
// 0 : not search
// 1 : not to circle
// 2 : to circle
int op = 0;
std::vector<int> dn(n);
auto dfs = [&](auto self, int u) -> int {
dn[u] = op;
f[u] = 1;
int fuck = 0;
for (auto v : e[u]) {
if (dn[v] == 0) {
fuck |= self(self, v);
} else if (dn[v] == op) {
fuck = 1;
}
if (f[v] == 2) {
fuck = 1;
}
}
if (fuck) {
f[u] = 2;
}
return fuck;
};
for (int i = 0; i < n; i ++) {
if (! f[i]) {
op = i + 1;
dfs(dfs, i);
}
}
while (q --) {
int x;
std::cin >> x;
x = (x % n + n) % n;
std::cout << (f[x] == 2 ? "Yes\n" : "No\n");
}
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
// std::cin >> t;
while (t --) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3820kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
Yes Yes No
result:
ok 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
3 2 3 1 1 -1 0 1 2 3
output:
No No No
result:
ok 3 tokens
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3588kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No Yes No
result:
wrong answer 2nd words differ - expected: 'No', found: 'Yes'