QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#789531#9810. Obliviate, Then Reincarnatewanghai673#WA 2ms11948kbC++201.8kb2024-11-27 20:43:382024-11-27 20:43:39

Judging History

This is the latest submission verdict.

  • [2024-11-27 20:43:39]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 11948kb
  • [2024-11-27 20:43:38]
  • Submitted

answer

#include<bits/stdc++.h>  
using namespace std;  
typedef long long LL;
const int N = 5e5 + 10,M = 1e6 + 10;  

LL w[M];
int h[N],e[M],ne[M],idx;  
void add(int a,int b,int c){  
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++;  
}  
LL d[N];
int dfn[N],low[N],stk[N],top,ts,id[N],scc;  
bool ins[N],inf[N];  
int n,m;  
void tarjan(int u){  
    dfn[u] = low[u] = ++ts;  
    stk[++top] = u,ins[u] = true;  
    for(int i = h[u];~i;i=ne[i]){  
        int j = e[i];  
        if(!dfn[j]){  
            d[j] = d[u] + w[i];
            tarjan(j);
            low[u] = min(low[j],low[u]);  
        }  
        else if(ins[j]){  
            if(d[u]-d[j]+w[i] != 0)inf[u] = 1;
            low[u] = min(low[u],dfn[j]);  
        }  
        inf[u] |= inf[j];
    }  
    if(dfn[u] == low[u]){
        int flg = 0;
        for(int i = 1;i<=top;++i)flg|=inf[stk[i]];
        ++scc;  
        int y;  
        do{  
            y = stk[top--];  
            // cout<<y<<"\n";  
            ins[y] = false;  
            inf[y] |= flg;
            id[y] = scc;  
        }while(y!=u);  
        // puts("");  
    }  
}  
int main(){
    // freopen("a.txt","r",stdin);
    int q;
    scanf("%d%d%d",&n,&m,&q);  
    memset(h,-1,sizeof h);  
    for(int i = 1;i<=m;++i){  
        int a,b;  
        int w;       
        scanf("%d%d",&a,&b);  
        w = b;
        a=(a%n+n)%n;
        b+=a;
        b=(b%n+n)%n;
        // cout<<a<<" "<<b<<" "<<w<<'\n';
        add(a,b,w);  
    }  
    for(int i = 1;i<=n;++i){  
        if(!dfn[i]){
            tarjan(i);  
        }
    }  
    while(q--){
        int x;
        scanf("%d",&x);
        x=(x%n+n)%n;
        if(inf[x])puts("Yes");
        else puts("No");
    }
    return 0;  
}  

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 9984kb

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

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: -100
Wrong Answer
time: 2ms
memory: 11948kb

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'