QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#885267 | #9810. Obliviate, Then Reincarnate | wol_qwq | WA | 0ms | 16096kb | C++20 | 1.5kb | 2025-02-06 15:01:35 | 2025-02-06 15:01:37 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct edge{
int to,nxt,w;
}e[maxn];
int n,m,q,cnt,head[maxn],dfn[maxn],tot,low[maxn],dep[maxn];
bool ans[maxn],vis[maxn];
void add(int u,int v,int w){
// cout<<u<<" "<<v<<" "<<w<<"\n";
e[++cnt].nxt=head[u];
head[u]=cnt;
e[cnt].to=v;
e[cnt].w=w;
}
stack<int>stk;
void tarjan(int x){
dfn[x]=low[x]=tot++;
vis[x]=1;
stk.push(x);
for(int i=head[x];i;i=e[i].nxt){
if(dfn[e[i].to]==-1){
dep[e[i].to]=dep[x]+e[i].w;
tarjan(e[i].to);
low[x]=min(low[x],low[e[i].to]);
}
else if(vis[e[i].to]){
if(dep[x]-dep[e[i].to]+e[i].w){
// cerr<<"tmp\n";
ans[x]=1;
}
low[x]=min(low[x],dfn[e[i].to]);
}
ans[x]|=ans[e[i].to];
}
if(dfn[x]==low[x]){
bool flag=ans[x];
queue<int>p;
while(stk.top()!=x) {
p.push(stk.top());
flag|=ans[stk.top()];
vis[stk.top()]=0;
stk.pop();
}
while(!p.empty()){
ans[p.front()]=flag;
p.pop();
}
vis[x]=0;
stk.pop();
}
stk.push(x),vis[x]=1;
for(int i=1;i<=n;i++){
if(dfn[i]==-1){
tarjan(i);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
memset(dfn,-1,sizeof(dfn));
memset(low,-1,sizeof(low));
cin>>n>>m>>q;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
x=(x%n+n)%n;
add(x,((x+y)%n+n)%n,y);
}
for(int i=1;i<=m;i++){
if(dfn[i]==-1){
tarjan(i);
}
}
while(q--){
int x;
cin>>x;
x=(x%n+n)%n;
cout<<(ans[x]?"Yes\n":"No\n");
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 16096kb
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: 16096kb
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: 0ms
memory: 16096kb
input:
1 1 1 0 1000000000 -1000000000
output:
No
result:
wrong answer 1st words differ - expected: 'Yes', found: 'No'