QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782348#9810. Obliviate, Then ReincarnatedreamjokerWA 2426ms31568kbC++232.9kb2024-11-25 19:48:572024-11-25 19:48:58

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 19:48:58]
  • Judged
  • Verdict: WA
  • Time: 2426ms
  • Memory: 31568kb
  • [2024-11-25 19:48:57]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;

using ll = long long ;
using pii = pair<ll,ll>;

const ll inf = numeric_limits<ll>::max()>>1;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int n,m,Q; cin>>n>>m>>Q;
    vector<vector<pii>> e(n+1);
    for(int i=0;i<m;i++) {
        int u,v,w; cin>>u>>w;
        v=((u+w)%n+n)%n;
        u=(u%n+n)%n;
        e[u].push_back({w,v});
    }

    vector<int> dfn(n+1),low(n+1),instk(n+1),scc(n+1);
    int cur=0,tot=0;
    vector<vector<int>> st;
    stack<int> stk;

    auto tarjan=[&](auto &&self,int x)->void {
        dfn[x]=low[x]=++cur;
        stk.push(x); instk[x]=1;

        for(auto [w,y]:e[x]) {
            if(!dfn[y]) {
                self(self,y);
                low[x]=min(low[x],low[y]);
            } else if(instk[y]) low[x]=min(low[x],dfn[y]);
        }

        if(dfn[x]==low[x]) {
            st.push_back({}); auto &v=st.back();
            int y;
            do {
                y=stk.top(); stk.pop();
                instk[y]=0;
                v.push_back(y);
                scc[y]=tot;
            } while(y!=x);
            tot++;
        }
    };

    for(int i=0;i<n;i++) {
        if(!dfn[i]) tarjan(tarjan,i);
    }

    vector<int> inque(n+1),cnt(n+1);
    vector<ll> dist(n+1);
    queue<int> q;
    auto judge=[&](int s,int o) {
        int id=scc[s];
        for(int x:st[id]) {
            inque[x]=0; cnt[x]=0; dist[x]=inf;
        }
        while(!q.empty()) q.pop();

        q.push(s); dist[s]=0; inque[s]=1;
        int tim=0;
        while(!q.empty()) {
            int u=q.front(); q.pop();
            inque[u]=0;
            tim++;
            if(tim>=st[id].size()*100) return false;

            for(auto [w,v]:e[u]) if(scc[v]==id) {
                if(o) w=-w;
                if(dist[v]>dist[u]+w) {
                    dist[v]=dist[u]+w;
                    cnt[v]=cnt[u]+1;

                    if(cnt[v]>=st[id].size()) {
                        return true;
                    }

                    if(!inque[v]) {
                        inque[v]=1;
                        q.push(v);
                    }
                }
            }
        }
        return false;
    };  

    vector<int> flag(n+1);
    for(int i=0;i<tot;i++) {
        for(int x:st[i]) {
            for(auto [w,y]:e[x]) 
                if(flag[scc[y]]) {
                    flag[i]=1;
                    break;
                }
            if(flag[i]) break;
        }
        if(!flag[i]) flag[i]|=judge(st[i].back(),0);
        if(!flag[i]) flag[i]|=judge(st[i].back(),1);

        // cout<<"scc: "<<i<<" "<<flag[i]<<endl;
        // for(int x:st[i]) cout<<x<<' ';
        // cout<<endl;
    }

    while(Q--) {
        int x; cin>>x;
        x=(x%n+n)%n;
        cout<<(flag[scc[x]]?"Yes":"No")<<'\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

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

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: 156ms
memory: 24920kb

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: 2426ms
memory: 31568kb

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'