QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#789531 | #9810. Obliviate, Then Reincarnate | wanghai673# | WA | 2ms | 11948kb | C++20 | 1.8kb | 2024-11-27 20:43:38 | 2024-11-27 20:43:39 |
Judging History
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'