QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#793372 | #9810. Obliviate, Then Reincarnate | LittleXi# | WA | 0ms | 7956kb | C++20 | 2.0kb | 2024-11-29 19:06:29 | 2024-11-29 19:06:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rof(i,a,b) for(int i=(a);i>=(b);i--)
#define wln putchar('\n')
#define pii pair<int,int>
#define ll long long
const int N=500005,B=19;
int n,m,q;
int fa[N],dfn[N],low[N],now,sta[N],top,col[N],ccnt;
int ind[N];
ll dis[N];
bool insta[N],f[N],ff[N];
vector<pii> e[N];
vector<int> e2[N];
void tarjan(int x)
{
dfn[x]=low[x]=++now;
sta[++top]=x;
insta[x]=1;
for(auto [y,z]:e[x])
if(!dfn[y])
{
fa[y]=x;
dis[y]=dis[x]+z;
tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(insta[y])
{
low[x]=min(low[x],sta[y]);
if(dis[x]-dis[y]+z!=0)f[x]=1;
}
if(low[x]==dfn[x])
{
col[x]=++ccnt;
while(sta[top]!=x)
{
int y=sta[top];
col[y]=ccnt;
insta[y]=0;
ff[ccnt]|=f[y];
top--;
}
insta[x]=0;
ff[ccnt]|=f[x];
top--;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
For(i,1,m)
{
int x,y,z;
scanf("%d%d",&x,&z);
y=x+z;
x=(x%n+n)%n;
y=(y%n+n)%n;
e[x].push_back({y,z});
}
For(i,0,n-1)
if(!dfn[i])tarjan(i);
For(i,0,n-1)
for(auto [j,k]:e[i])
{
int x=col[i],y=col[j];
if(x!=y)
{
e2[y].push_back(x);
ind[x]++;
}
}
For(i,1,ccnt)
if(ind[i]==0)sta[++top]=i;
while(top)
{
int x=sta[top]; top--;
for(int y:e2[x])
{
ff[y]|=ff[x];
ind[y]--;
if(ind[y]==0)sta[++top]=y;
}
}
For(i,1,q)
{
int x;
scanf("%d",&x);
x=(x%n+n)%n;
if(ff[col[x]])printf("Yes\n");
else printf("No\n");
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7956kb
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: 7868kb
input:
3 2 3 1 1 -1 0 1 2 3
output:
No No No
result:
ok 3 tokens
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 5892kb
input:
1 1 1 0 1000000000 -1000000000
output:
No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'