QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#782463#9810. Obliviate, Then ReincarnatedreamjokerWA 0ms3880kbC++232.3kb2024-11-25 20:09:002024-11-25 20:09:01

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 20:09:01]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3880kb
  • [2024-11-25 20:09:00]
  • Submitted

answer

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("unroll-loops")

#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> vis(n+1);
    vector<ll> h(n+1);

    auto judge=[&](auto &&self,int x,ll dis)->bool {
        h[x]=dis; vis[x]=1;
        for(auto [w,y]:e[x]) if(scc[y]==scc[x]) {
            if(!vis[y]) {if(!self(self,y,h[x]+w)) return true;}
            else if(h[y]!=h[x]+w) return true;
        }
        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(y==x&&w!=0) {
                    flag[i]=1;
                    break;
                }
            }
            if(flag[i]) break;
        }
        if(!flag[i]) flag[i]|=judge(judge,st[i].back(),0);

    }

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

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

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

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3640kb

input:

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

output:

No
Yes
No

result:

wrong answer 2nd words differ - expected: 'No', found: 'Yes'