QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#793343#9810. Obliviate, Then ReincarnateLittleXi#WA 159ms20052kbC++201.4kb2024-11-29 18:50:002024-11-29 18:50:01

Judging History

This is the latest submission verdict.

  • [2024-11-29 18:50:01]
  • Judged
  • Verdict: WA
  • Time: 159ms
  • Memory: 20052kb
  • [2024-11-29 18:50:00]
  • 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;
ll dis[N];
bool insta[N],f[N];
vector<pii> e[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]);
            f[x]|=f[y];
        }
        else if(insta[y])
        {
            low[x]=min(low[x],sta[y]);
            if(dis[x]-dis[y]+z!=0)f[x]=1;
        }
        else f[x]|=f[y];
    if(low[x]==dfn[x])
    {
        while(sta[top]!=x)
        {
            insta[sta[top]]=0;
            top--;
        }
        insta[x]=0;
        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,1,q)
    {
        int x;
        scanf("%d",&x);
        x=(x%n+n)%n;
        if(f[x])printf("Yes\n");
        else printf("No\n");
    }
}

Details

Tip: Click on the bar to expand more detailed information

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: 7908kb

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: 1ms
memory: 5764kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 1ms
memory: 7868kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Wrong Answer
time: 159ms
memory: 20052kb

input:

50134 500000 500000
-154428638 -283522863
-186373509 -327130969
154999046 46750274
-933523447 349415487
-437683609 140099255
864996699 -262318199
811293034 -264299324
120273173 52410685
874944410 -52048424
445049930 -803690605
-138111276 -104634331
720288580 126597671
471164416 -348777147
-356502322...

output:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

wrong answer 70268th words differ - expected: 'No', found: 'Yes'