QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#797319#9810. Obliviate, Then ReincarnatecodingforchineseRE 676ms52660kbC++142.0kb2024-12-02 20:45:402024-12-02 20:45:40

Judging History

This is the latest submission verdict.

  • [2024-12-02 20:45:40]
  • Judged
  • Verdict: RE
  • Time: 676ms
  • Memory: 52660kb
  • [2024-12-02 20:45:40]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=500010,B=19;
int n,m,q;
int fa[N],dfn[N],low[N],now,sta[N],top,col[N],ccnt;
int ind[N];
int dis[N];
bool insta[N],f[N],ff[N];
vector<pair<int,int>>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],dfn[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--;
    }
}
signed main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>z;
        y=x+z;
        x=(x%n+n)%n;
        y=(y%n+n)%n;
        e[x].push_back({y,z});
    }
    for(int i=0;i<=n-1;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    for(int i=0;i<=n-1;i++)
    {
        for(auto [j,k]:e[i])
        {
            int x=col[i];
            int y=col[j];
            if(x!=y)
            {
                e2[y].push_back(x);
                ind[x]++;
            }
        }
        for(int i=1;i<=ccnt;i++)
        {
            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(int i=1;i<=q;i++)
    {
        int x;
        cin>>x;
        x=(x%n+n)%n;
        if(ff[col[x]])cout<<"Yes\n";
        else cout<<"No\n";
    }

}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 30820kb

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: 4ms
memory: 30384kb

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: 0ms
memory: 28736kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 5ms
memory: 27968kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: 0
Accepted
time: 676ms
memory: 52660kb

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:

ok 500000 tokens

Test #6:

score: -100
Runtime Error

input:

100848 500000 500000
720352587 361776806
231853504 -933882325
960971230 -83519300
-152772415 -631132247
842871215 -666621297
857194330 -754943024
-698506963 -705416545
-3551931 -927937446
628710320 -942247987
674921043 847145884
-325629529 475694308
-339363446 686789318
236702996 654762989
420412365...

output:


result: