QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#885267#9810. Obliviate, Then Reincarnatewol_qwqWA 0ms16096kbC++201.5kb2025-02-06 15:01:352025-02-06 15:01:37

Judging History

This is the latest submission verdict.

  • [2025-02-06 15:01:37]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 16096kb
  • [2025-02-06 15:01:35]
  • Submitted

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'