QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#796992#9810. Obliviate, Then ReincarnateWzyWA 245ms40060kbC++142.9kb2024-12-02 13:46:572024-12-02 13:46:59

Judging History

This is the latest submission verdict.

  • [2024-12-02 13:46:59]
  • Judged
  • Verdict: WA
  • Time: 245ms
  • Memory: 40060kb
  • [2024-12-02 13:46:57]
  • 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];
LL f[N],ft[N],ans[N];
LL w[M];


void add(int a, int b,int c)
{
    w[idx]=c,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)%n;
}

bool check(int u){
    int hh=0,tt=0;
    f[0]=u;
    ft[u]=true;

    while(hh<=tt){
        int v=f[hh++];

        for(int i=h[v];~i;i=ne[i]){
            int j=e[i];
            if(id[j]!=id[v]) continue;

            if(ft[j]){
                if(ans[j]==ans[v]+w[i]) continue;
                return true;
            }

            ft[j]=true;
            ans[j]=ans[v]+w[i];
            f[++tt]=j;
        }
    }

    return false;
}



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

    vector<int> root;

    while(m--){
        int a,b;
        cin>>a>>b;
        int g=b;
        if(b==0) continue;

        b=a+b;
        if(a<0) a=get_mod(a);
        else a%=n;
        if(b<0) b=get_mod(b);
        else b=b%n;
        //cout<<a<<" "<<b<<endl;
        if(a==b) root.push_back(a);
        else add(b,a,g);

    }


    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++) cout<<id[i]<<" ";
    //cout<<endl;
    
    for(int i=0;i<n;i++) a[id[i]].push_back(i);
    for(int i=1;i<=scc_cnt;i++) if(check(a[i][0])) st[i]=true;

    for(int i=scc_cnt;i>0;i--){
        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;
        //cout<<x<<endl;
        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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 4ms
memory: 20116kb

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: 239ms
memory: 33668kb

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
Wrong Answer
time: 245ms
memory: 40060kb

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:

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 1st words differ - expected: 'Yes', found: 'No'