QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#794165 | #9810. Obliviate, Then Reincarnate | MYdinosaur | WA | 4ms | 30164kb | C++14 | 2.8kb | 2024-11-30 12:27:02 | 2024-11-30 12:27:02 |
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;
sdf[y].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++)
{
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 30164kb
input:
3 2 3 1 1 -1 3 1 2 3
output:
No No No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'