QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#793372#9810. Obliviate, Then ReincarnateLittleXi#WA 0ms7956kbC++202.0kb2024-11-29 19:06:292024-11-29 19:06:29

Judging History

This is the latest submission verdict.

  • [2024-11-29 19:06:29]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 7956kb
  • [2024-11-29 19:06:29]
  • Submitted

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'