QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#782664 | #9810. Obliviate, Then Reincarnate | Andyqian7 | WA | 317ms | 47380kb | C++20 | 2.4kb | 2024-11-25 20:55:19 | 2024-11-25 20:55:25 |
Judging History
This is the latest submission verdict.
- [2024-11-26 23:19:26]
- hack成功,自动添加数据
- (/hack/1260)
- [2024-11-25 20:55:19]
- Submitted
answer
#include <bits/stdc++.h>
#define int long long
#define rep(i, s, e) for (int i = s; i <= e; i++)
using namespace std;
const int N = 1e6 + 10;
vector<int> e[N], sta, com[N], ie[N];
int n, m, q, dfn[N], low[N], f[N], vis[N], dfsOrder, sccnum, ok[N], val[N];
void tarjan(int u)
{
dfn[u] = low[u] = ++dfsOrder;
sta.push_back(u);
vis[u] = 1;
for (auto &v : e[u])
{
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] != low[u])
return;
++sccnum;
vector<int>::iterator it = (--sta.end());
for (f[u] = sccnum, vis[u] = 0; *it != u; --it)
f[*it] = sccnum, vis[*it] = 0;
sta.erase(it, sta.end());
}
struct edge
{
int to, val;
};
vector<edge> g[N];
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> n >> m >> q;
rep(i, 1, m)
{
int a, b;
cin >> a >> b;
int c = b;
a = (a % n + n) % n, b = (b % n + n) % n;
e[a + 1].push_back((a + b) % n + 1);
ie[(a + b) % n + 1].push_back(a + 1);
g[a + 1].push_back({(a + b) % n + 1, c});
}
rep(i, 1, n) if (!dfn[i]) tarjan(i);
rep(i, 1, n)
{
com[f[i]].push_back(i);
}
rep(i, 1, n)
vis[i] = 0;
rep(i, 1, sccnum)
{
queue<int> Q;
for (int j : com[i])
{
Q.push(j);
}
while (Q.size())
{
int t = Q.front();
Q.pop();
vis[t] = 1;
for (auto [son, dis] : g[t])
{
if (f[son] != f[t])
continue;
if (vis[son])
{
if (val[son] != val[t] + dis)
ok[i] = 1;
}
else
{
val[son] = val[t] + dis;
Q.push(son);
}
}
}
if (ok[i])
for (int j : com[i])
{
for (int k : ie[j])
{
ok[f[k]] = 1;
}
}
}
while (q--)
{
int x;
cin >> x;
x = (x % n + n) % n;
cout << (ok[x + 1] ? "Yes" : "No") << endl;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 9668kb
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: 4ms
memory: 9716kb
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: 5ms
memory: 11996kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: 0
Accepted
time: 5ms
memory: 9760kb
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000
output:
No No No
result:
ok 3 tokens
Test #5:
score: -100
Wrong Answer
time: 317ms
memory: 47380kb
input:
50134 500000 500000 -154428638 -283522863 -186373509 -327130969 154999046 46750274 -933523447 349415487 -437683609 140099255 864996699 -262318199 811293034 -264299324 120273173 52410685 874944410 -52048424 445049930 -803690605 -138111276 -104634331 720288580 126597671 471164416 -348777147 -356502322...
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:
wrong answer 55056th words differ - expected: 'No', found: 'Yes'