QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#885671#9810. Obliviate, Then ReincarnatefurrywolfRE 0ms18148kbC++201.6kb2025-02-06 17:05:132025-02-06 17:05:15

Judging History

This is the latest submission verdict.

  • [2025-02-06 17:05:15]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 18148kb
  • [2025-02-06 17:05:13]
  • Submitted

answer

#include<bits/stdc++.h>
#define ll long long
#define R register int
#define if(x) if(__builtin_expect(x,1))
#define while(x) while(__builtin_expect(x,1))
using namespace std;
const int N=1e6+1;
int n,m,q;
struct node{int to,nxt,w;}e[N];
int head[N],dfn[N],low[N],tot,ts,dep[N];
bool vis[N],ans[N];stack<int>s;
void add(int u,int v,int w){e[++tot]={v,head[u],w};head[u]=tot;}
void tarjan(int u){
    dfn[u]=low[u]=++ts;s.push(u);vis[u]=1;
    for(R i=head[u]; i; i=e[i].nxt){
        int v=e[i].to;
        if(dfn[v]==-1)dep[v]=dep[u]+e[i].w,tarjan(v),low[u]=min(low[u],low[v]);
        else if(vis[v]){
            if(dep[u]-dep[v]+e[i].w!=0)ans[u]=1;
            low[u]=min(low[u],dfn[v]);
        }
        ans[u]|=ans[v];
    }
    if(low[u]==dfn[u]){
        vector<int>v;v.clear();
        int now=ans[u];
        while(s.top()!=u){
            vis[s.top()]=0;
            v.push_back(s.top());
            now|=ans[s.top()];
            s.pop();
        }
        s.pop();vis[u]=0;
        for(auto i:v)ans[i]=now;
    }
}
int main(){
    #ifdef ONLINE_JUDGE
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    #endif
    memset(low,-1,sizeof low);
    memset(dfn,-1,sizeof dfn);
    cin>>n>>m>>q;
    for(R i=1,u,v; i<=m; i++)
        cin>>u>>v,add((u%n+n)%n,((u+v)%n+n)%n,v);
    for(R i=0; i<n; i++)
        if(dfn[i]==-1)tarjan(i);
    // for(R i=1; i<=n; i++)cout<<dfn[i]<<' ';cout<<'\n';
    // for(R i=1; i<=n; i++)cout<<low[i]<<' ';cout<<'\n';
    while(q--){
        int x;cin>>x;
        cout<<(ans[(x+n)%n]?"Yes":"No")<<'\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Runtime Error

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:


result: