QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#796950#9810. Obliviate, Then ReincarnateWzyWA 3ms16368kbC++142.3kb2024-12-02 12:28:112024-12-02 12:28:12

Judging History

This is the latest submission verdict.

  • [2024-12-02 12:28:12]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 16368kb
  • [2024-12-02 12:28:11]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
typedef  long long LL;
typedef pair<LL,int> PII;
const int N=1e6+10,M=2*N;
const int mod=998244353;
int h[N],e[M],ne[M],idx;
int st[N];
int n,m,q;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int id[N], scc_cnt, Size[N];
int dout[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp;
    stk[ ++ top] = u, in_stk[u] = true;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
    }

    if (dfn[u] == low[u])
    {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++ ;
        } while (y != u);
    }
}

int get_mod(int x){
    int t=-x%n;

    return n-t;
}



void solve(){
    cin>>n>>m>>q;
    memset(h,-1,sizeof h);

    map<PII,int> mp;
    vector<int> root;

    while(m--){
        int a,b;
        cin>>a>>b;
        if(b==0) continue;
        if(a<0) a=get_mod(a);
        else a%=n;
        b=(a+b)%n;
        //cout<<a<<" "<<b<<endl;
        if(a==b) root.push_back(a);
        else if(mp[{b,a}]) continue;
        else add(b,a),mp[{b,a}]=true;

    }


    for(int i=0;i<n;i++) if(!id[i]) tarjan(i);

    for(auto t:root) st[id[t]]=true;
    //cout<<id[1]<<endl;


    vector<int> a[scc_cnt+1];

    
    for(int i=0;i<n;i++) a[id[i]].push_back(i);

    for(int i=scc_cnt;i>0;i--){
        if(Size[i]>1) st[i]=true;
        for(auto u:a[i]){
            for(int i=h[u];~i;i=ne[i]){
                int j=e[i];
                //cout<<id[u]<<" "<<id[j]<<endl;
                j=id[j];

                st[j]=st[id[u]];
            }
        }
    }

    while(q--){
        int x;
        cin>>x;
        if(x<0) x=get_mod(x);
        else x%=n;

        if(st[id[x]]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }

}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    //cin>>T;

    while(T--) solve();
 
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 16368kb

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'