QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#796623 | #9810. Obliviate, Then Reincarnate | MYdinosaur | ML | 4ms | 38680kb | C++14 | 3.4kb | 2024-12-01 22:26:54 | 2024-12-01 22:27:01 |
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];
ll 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 < v[x].size(); i++)
{
int y = v[x][i].first;
if (abc[y] == 1)
{
abc[x] = abc[y];
return;
}
dfs(y);
if (abc[y] == 1)
{
abc[x] = abc[y];
return;
}
}
}
int work(int fa, int da)
{
if (abc[fa] == 1) return 1;
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;
// cout << x << " " << f[x] << " " << y << " " << f[y] << " " << z << endl;
if (bj[y] != da) continue;
if (abc[y] == 1) return 1;
if (f[y] == -1)
{
f[y] = f[x] + z;
q.push(y);
}
else if (f[y] != f[x] + z) return 1;
}
}
return 0;
}
int main()
{
// freopen("in.txt","r",stdin);
// freopen("1.txt","w",stdout);
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 << " " << y << endl;
if (x == t)
{
abc[x] = 1;
}
else
{
v[x].push_back({t, y});
}
}
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 = 0; i < n; i++)
{
if (abc[i] == 1 || na[bj[i]] == 1) abc[i] = 1;
}
for (int i = 0; i < n; i++)
{
if (abc[i] == 0) dfs(i);
}
for (int i = 1; i <= qe; i++)
{
ll x;
read(x);
x = x % n;
x = (x + n) % n;
if (abc[x] == 1) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 4ms
memory: 38416kb
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: 36404kb
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: 38680kb
input:
1 1 1 0 1000000000 -1000000000
output:
Yes
result:
ok "Yes"
Test #4:
score: -100
Memory Limit Exceeded
input:
3 2 3 0 1000000000 1 -1000000000 -1000000000 0 -1000000000