QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#788992#9810. Obliviate, Then Reincarnatejdyt11ML 5ms16132kbC++232.3kb2024-11-27 18:58:532024-11-27 18:58:54

Judging History

This is the latest submission verdict.

  • [2024-11-27 18:58:54]
  • Judged
  • Verdict: ML
  • Time: 5ms
  • Memory: 16132kb
  • [2024-11-27 18:58:53]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define inf 0x3f3f3f3f
#define ull unsigned long long
#define pll pair<ll,ll>
#define ls d*2
#define rs d*2+1
#define mid (l+r)/2
#define lowbit(x) (x&(-x))
//#define endl "\n"
#define all(x) x.begin(),x.end()
#define int long long
//mt19937 seed;
//uniform_int_distribution<int>num(0,2e9);
const int N=1e6+10;
const int M=33;


int n,m,q;
vector<pii>e[N];
vector<int>fan[N],scc[N];
int cnt,id[N],insta[N];
stack<int>s;
int low[N],dfn[N],dep;
int is[N],ans[N];
int ru[N];
bool dfs(int qi,int now,int u,vector<int>vis){
	for(auto [v,w]:e[u]){
		if(id[u]==id[v]&&!vis[v]){
			vis[v]=1;
			if(v==qi&&now+w!=0)return 1;
			if(dfs(qi,now+w,v,vis))return 1;
			vis[v]=0;
		}
	}
	return 0;
}
void tarjan(int u){
	dfn[u]=low[u]=++dep;
	s.push(u);
	insta[u]=1;
	for(auto [v,w]:e[u]){
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(insta[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int y;
		cnt++;
		int tot=0;
		while(1){
			y=s.top();
			s.pop();
			insta[y]=0;
			tot++;
			id[y]=cnt;
			if(u==y)break;
		}
		vector<int>vis(n+1,0);
		vis[u]=1;
		if((tot==1&&is[u])||(tot>1&&dfs(u,0,u,vis)))ans[cnt]=1;
	}
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int _=1;//cin>>_;
    while(_--){
    	cin>>n>>m>>q;
    	int temp=1e10;
    	for(int i=0;i<m;i++){
    		int a,b;
    		cin>>a>>b;
    		if(b==0)continue;
    		int u=a+temp*n;
    		u%=n;
    		if(u==0)u=n;
    		int v=a+b+temp*n;
    		v%=n;
    		if(v==0)v=n;
    		if(u==v){
    			is[u]=1;
    			continue;
			}
    		e[u].push_back({v,b});
    		fan[v].push_back(u);
		}
		for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
		for(int u=1;u<=n;u++){
			for(int v:fan[u]){
				if(id[u]!=id[v])scc[id[u]].push_back(id[v]),ru[id[v]]++;
			}
		}
		queue<int>qq;
		for(int i=1;i<=cnt;i++)if(!ru[i])qq.push(i);
		while(qq.size()){
			int u=qq.front();
			qq.pop();
			for(int v:scc[u]){
				ru[v]--;
				if(!ru[v])qq.push(v);
				ans[v]|=ans[u];
			}
		}
		while(q--){
			int x;
			cin>>x;
			x=x+temp*n;
			x%=n;
			if(x==0)x=n;
			if(ans[id[x]])cout<<"Yes"<<endl;
			else cout<<"No"<<endl;
		}		
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 16132kb

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: 2ms
memory: 11816kb

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: 2ms
memory: 15804kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 5ms
memory: 11708kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: -100
Memory 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: