QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#785511#9810. Obliviate, Then ReincarnateTom22lTL 1ms5796kbC++171.5kb2024-11-26 18:07:082024-11-26 18:07:09

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 18:07:09]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 5796kb
  • [2024-11-26 18:07:08]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
int Read(){
	int x=0;
	char ch=getchar();bool f=0;
	while(ch<'0'||ch>'9') if(ch=='-')f=1,ch=getchar(); else if(ch==EOF)return 0; else ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
int h[1000005];
int nxt[1000005];
int to[1000005];
int cnt;
int ans[1000005];
void link(int x,int y){
	nxt[++cnt]=h[x];
	h[x]=cnt;
	to[cnt]=y;
	return ;
}
bool vis[500005];
int pth[500005];
int n,m,q;
bool dfs(int x){
//	cout<<x<<':'<<endl;
	vis[x]=1;
	for(int i=h[x];i;i=nxt[i]){
		int y=to[i];
		int k=((x+y)%n+n)%n;
//		cout<<y<<' '<<k<<endl;
		if(ans[k]==1){
			ans[x]=1;
			return 1;
		}if(ans[k]==2) continue;
		if(vis[k]){
			if(pth[x]-pth[k]+y){
//				cout<<x<<' '<<k<<' '<<pth[x]<<' '<<pth[k]<<' '<<y<<endl;
				ans[k]=1;ans[x]=1;return 1;
			}else continue;
		}
		pth[k]=pth[x]+y;
		if(dfs(k)){
			ans[x]=1;return 1;
		}vis[k]=0;
	}
//	cout<<"end";
	return 0;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	n=Read(),m=Read(),q=Read();
	while(m--){
		int x=Read(),y=Read();
		x=(x%n+n)%n;
		link(x,y);
	}
	for(int i=0;i<n;i++){
		if(!ans[i]){
			dfs(i);
		} 
	}while(q--){
		int x=Read();x=(x%n+n)%n;
		if(ans[x]==1) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
// 1 1  dfs(1) -> dfs(2) pth[2]=1;
// 2 1    -> 3 pth=0   pth[3]=2;
// 3 -2   -> 1 pth[3]-pth[1]+y(2->3) == 0 
// 3 -> 2

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5732kb

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: 1ms
memory: 5720kb

input:

3 2 3
1 1
-1 0
1
2
3

output:

No
No
No

result:

ok 3 tokens

Test #3:

score: 0
Accepted
time: 1ms
memory: 5796kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 1ms
memory: 5788kb

input:

3 2 3
0 1000000000
1 -1000000000
-1000000000
0
-1000000000

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Time Limit Exceeded

input:

50134 500000 500000
-154428638 -283522863
-186373509 -327130969
154999046 46750274
-933523447 349415487
-437683609 140099255
864996699 -262318199
811293034 -264299324
120273173 52410685
874944410 -52048424
445049930 -803690605
-138111276 -104634331
720288580 126597671
471164416 -348777147
-356502322...

output:


result: