QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788665#9810. Obliviate, Then ReincarnateMaxduanWA 0ms11692kbC++202.2kb2024-11-27 17:49:072024-11-27 17:49:10

Judging History

This is the latest submission verdict.

  • [2024-11-27 17:49:10]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 11692kb
  • [2024-11-27 17:49:07]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define maxn 500005
#define int 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];
int ok[maxn];
int 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;
        }
    }
}

int dp[maxn],nows;

void dfs1(int u){
    for(auto [w,v]:g[u]){
        if(scc[v]!=nows)continue;
        if(dp[v]!=-1){
            //cout<<"u v w dp="<<u<<' '<<v<<' '<<w<<' '<<dp[u]<<' '<<dp[v]<<'\n';
            if(dp[v]!=dp[u]+w){
                ok[nows]=1;
            }
        }
        else{
            dp[v]=dp[u]+w;
            dfs1(v);
        }
    }
}

void dfs2(int u){
    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;
        //cout<<"a nxt"<<' '<<a<<' '<<nxt<<'\n';
        g[a].push_back({b,nxt});
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }

    for(int i=1;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=1;i<=n;i++){
        dp[i]=-1;
        //cout<<"i scc="<<i<<' '<<scc[i]<<'\n';
    }

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

    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: 0
Wrong Answer
time: 0ms
memory: 11692kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

YES
YES
NO

result:

wrong answer 1st words differ - expected: 'Yes', found: 'YES'