QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#794173 | #9810. Obliviate, Then Reincarnate | MYdinosaur | WA | 4ms | 40424kb | C++14 | 3.0kb | 2024-11-30 12:33:50 | 2024-11-30 12:33:51 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, ll> pa;
const int N = 5e5 + 10;
int spec = 0;
int abc[N], abcd[N], a[N];
int vis[N], dfn[N], low[N];
int cnt = 0, tot = 0;
vector <int> sdf[N];
vector <pa> v[N];
int bj[N];
int na[N];
int f[N];
stack <int> q;
inline void read(ll &x)
{
ll w = 1; x = 0; char ch = getchar();
while (!isdigit(ch)) {if (ch == '-') w = -1; ch = getchar();}
while (isdigit(ch)) {x = x * 10 + (ch ^ 48); ch = getchar();}
x = x * w;
}
void dg(int x)
{
vis[x] = 1;
cnt ++;
dfn[x] = low[x] = cnt;
q.push(x);
for (int i = 0; i < v[x].size(); i++)
{
int y = v[x][i].first;
if (abc[y] == 1) continue;
if (dfn[y] == 0)
{
dg(y);
low[x] = min(low[x], low[y]);
}
else if (!bj[y]) low[x] = min(low[x], dfn[y]);
}
if (dfn[x] == low[x])
{
tot ++;
a[tot] = x;
while (!q.empty())
{
int t = q.top();
q.pop();
bj[t] = tot;
if (t == x) break;
}
}
}
void dfs(int x)
{
for (int i = 0; i < sdf[x].size(); i++)
{
int y = sdf[x][i];
if (abc[y] == 1) continue;
abc[y] = 1;
dfs(y);
}
}
int work(int fa, int da)
{
int ind = 0;
queue <int> q;
f[fa] = 0;
q.push(fa);
while (!q.empty())
{
int x = q.front();
q.pop();
for (int i = 0; i < v[x].size(); i++)
{
int y = v[x][i].first;
int z = v[x][i].second;
if (bj[y] != da) continue;
if (f[y] == -1)
{
q.push(y);
}
else if (f[y] != f[x] + z) return 1;
}
}
return 0;
}
int main()
{
ll n, m, qe;
read(n); read(m); read(qe);
for (int i = 1; i <= m; i++)
{
ll x, y;
read(x); read(y);
if (y == 0) continue;
ll t = (x + y) % n;
x = x % n;
x = (x + n) % n;
t = (t + n) % n;
// cout << x << " " << t << endl;
sdf[t].push_back(x);
if (x == t)
{
spec++;
abc[x] = 1;
abcd[spec] = x;
}
else
{
v[x].push_back({t, y});
}
}
for (int i = 1; i <= spec; i++)
{
// cout << i << " " << sdf[i].size() << endl;
dfs(abcd[i]);
}
for (int i = 0; i < n; i++)
{
f[i] = -1;
if (abc[i] == 1) continue;
if (!vis[i]) dg(i);
}
for (int i = 1; i <= tot; i++)
{
int x = a[i];
na[i] = work(x, i);
}
for (int i = 1; i <= qe; i++)
{
ll x;
read(x);
x = x % n;
if (abc[x] == 1 || na[bj[x]] == 1) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 40424kb
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: 36380kb
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: 4ms
memory: 32288kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 34348kb
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'