QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789997#9810. Obliviate, Then ReincarnateocharinRE 0ms3548kbC++202.0kb2024-11-27 23:28:502024-11-27 23:28:56

Judging History

This is the latest submission verdict.

  • [2024-11-27 23:28:56]
  • Judged
  • Verdict: RE
  • Time: 0ms
  • Memory: 3548kb
  • [2024-11-27 23:28:50]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n,m,Q;
    cin>>n>>m>>Q;
    vector<vector<array<int,2>>>e(n+1);
    auto get=[&](int x)->int{
        return ((x%n)+n)%n;
    };
    for(int i=0;i<m;++i){
        int x,y;
        cin>>x>>y;
        int u=get(x);
        int v=get(x+y);
        e[u+1].push_back({v+1,y});
    }
    vector<int>dfn(n+1),low(n+1),vis(n+1),id(n+1),is(n+1),res(n+1),dis(n+1);
    int tot=0,tmp=0;
    stack<int>s;
    auto tarjan=[&](auto tarjan,int u)->void{
        dfn[u]=low[u]=++tot;
        s.push(u);
        vis[u]=1;
        for(auto [v,w]:e[u]){
            if(!dfn[v]){
                dis[v]=dis[u]+w;
                tarjan(tarjan,v);
                low[u]=min(low[u],low[v]);
            }
            else if(vis[v]){
                // cerr<<u<<" < "<<v<<" "<<w<<endl;
                if(dis[u]-dis[v]+w) is[u]=1;
                low[u]=min(low[u],dfn[v]);
            }
        }
        if(low[u]==dfn[u]){
            ++tmp;
            while(1){
                int x=s.top();s.pop();
                id[x]=tmp;
                res[tmp]|=is[x];
                vis[x]=0;
                if(x==u) break;
            }
        }
    };
    for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(tarjan,i);
    vector<int>in(tmp+1);
    vector<vector<int>>ee(tmp+1);
    for(int i=1;i<=n;++i){
        for(auto [j,k]:e[i]){
            if(id[i]==id[j]) continue;
            ee[id[j]].push_back(id[i]);
            in[id[i]]++;
        }
    }
    queue<int>q;
    for(int i=1;i<=tmp;++i) if(!in[i]) q.push(i);
    while(!q.empty()){
        auto u=q.front();q.pop();
        for(auto v:ee[u]){
            res[v]|=res[u];
            in[v]--;
            if(!in[v]) q.push(v);
        }
    }
    while(Q--){
        int x;
        cin>>x;
        cout<<(res[id[x+1]]?"Yes\n":"No\n");
    }
}

詳細信息

Test #1:

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

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: -100
Runtime Error

input:

1 1 1
0 1000000000
-1000000000

output:


result: