QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788714#9810. Obliviate, Then ReincarnateMaxduanRE 604ms36004kbC++202.0kb2024-11-27 18:01:082024-11-27 18:01:08

Judging History

This is the latest submission verdict.

  • [2024-11-27 18:01:08]
  • Judged
  • Verdict: RE
  • Time: 604ms
  • Memory: 36004kb
  • [2024-11-27 18:01:08]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
#define int long long
#define ll long long
#define pii pair<int,int>

vector<pii>g[maxn],g2[maxn];
stack<int>st;
int dn,dfn[maxn],low[maxn];
int scc[maxn],cnt;
bool instk[maxn];
bool ok[maxn];
bool vis[maxn];

void tarjan(int k)
{
    dfn[k]=low[k]=++dn;
    st.push(k),instk[k]=1;
    for(auto [len,x]:g[k])
    {
        if(!dfn[x])
        {
            tarjan(x);
            low[k]=min(low[k],low[x]);
        }
        else if(dfn[x]&&instk[x]) low[k]=min(low[k],dfn[x]);
    }
    if(dfn[k]==low[k])
    {
        cnt++;
        while(1)
        {
            int temp=st.top();
            st.pop();
            instk[temp]=0;
            scc[temp]=cnt;
            if(temp==k)break;
        }
    }
}

ll dp[maxn],nows;

void dfs1(int u){
    vis[u]=1;
    for(auto [w,v]:g[u]){
        if(scc[v]!=nows)continue;
        if(vis[v]){
            if(dp[v]!=dp[u]+w){
                ok[nows]=1;
            }
        }
        else{
            dp[v]=dp[u]+w;
            dfs1(v);
        }
    }
}

void dfs2(int u){
    vis[u]=1;
    for(auto [w,v]:g2[u]){
        if(!vis[v])dfs2(v);
        if(ok[v])ok[u]=1;
    }
}

signed main(){
    int n,m,q;cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int a,b;cin>>a>>b;
        a=(a%n+n)%n;
        int nxt=(a+b)%n;
        g[a].push_back({b,nxt});
    }
    for(int i=0;i<n;i++){
        if(!dfn[i]) tarjan(i);
    }

    for(int i=0;i<n;i++){
        for(auto [w,v]:g[i]){
            if(scc[i]==scc[v])continue;
            g2[scc[i]].push_back({w,scc[v]});
        }
    }

    
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        nows=scc[i];
        dfs1(i);
    }

    memset(vis,0,sizeof(vis));

    for(int i=1;i<=cnt;i++){
        if(!vis[i])dfs2(i);
    }

    for(int i=1;i<=q;i++){
        int x;cin>>x;
        x=(x%n+n)%n;
        if(ok[scc[x]]){
            cout<<"Yes\n";
        }
        else cout<<"No\n";
    }
    
    
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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: 2ms
memory: 10196kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 0ms
memory: 9792kb

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: 604ms
memory: 36004kb

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: