QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783083#9810. Obliviate, Then ReincarnateFHQYTL 190ms144240kbC++172.7kb2024-11-25 23:14:222024-11-25 23:14:23

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 23:14:23]
  • Judged
  • Verdict: TL
  • Time: 190ms
  • Memory: 144240kb
  • [2024-11-25 23:14:22]
  • Submitted

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define endl '\n'
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
const int N=1e6+5;

int n;
int vis[N],dfn[N],low[N],sk[N],top,num,cnt,col[N];
int viss[N],dis[N],cntt[N];
int in[N],out[N];
bool vs[N],fl[N];
vector<int>e[N],scc[N];
vector<pii>G[N],g[N];
void tarjan(int u){
	vis[sk[++top]=u]=1;
	dfn[u]=low[u]=++num;
	for(auto to:G[u]){
		int v=to.fi;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(vis[v])
			low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int v;cnt++;
		do{
			v=sk[top--];
			vis[v]=0;
			col[v]=cnt;
		}while(u!=v);
	}
}
bool spfa(int x,int op,vector<int> p){
	int inf=1e18;
	for(auto now : p)
	{
		viss[now]=0,dis[now]=inf*op;
	}
	dis[x]=0,cntt[x]=0;
	queue<int> q;
	q.push(x);
	while(!q.empty())
	{
		int now = q.front();
		q.pop();
		viss[now]=0;
		for(int i=0;i<g[now].size();i++)
		{
			pair<int,int> s=g[now][i];
			if(col[s.first]!=col[x])continue;
//			cout<<now<<' '<<s.first<<" ff"<<endl;
			if(dis[s.first]>dis[now]+s.second*op)
			{
				dis[s.first]=dis[now]+s.second*op;
				cntt[s.first]=cntt[now]+1;
				if(cntt[now]>=p.size()) return true;
				if(!viss[s.first]) viss[s.first]=1,q.push(s.first);
			}
		}
	}
	return false;
}
void solve(){
	cin>>n;
	int m,Q;
	cin>>m>>Q;
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		if(b==0)
			continue;
		a=(a%n+n)%n;
		G[a+1].push_back({((a+b)%n+n)%n+1,b});
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		scc[col[i]].push_back(i);
	for(int u=1;u<=n;u++){
		for(auto to:G[u]){
			int v=to.fi;
			if(col[u]==col[v])continue;
			in[col[u]]++;
			out[col[v]]++;
			e[col[v]].push_back(col[u]);
		}
	}
	for(int u=1;u<=n;u++){
		for(auto to:G[u]){
			int v=to.fi;
			if(col[u]!=col[v])continue;
			g[u].push_back({v,to.se});
		}
	}
//	for(int i=1;i<=cnt;i++){
//		cout<<"# ";
//		for(auto v:scc[i])
//			cout<<v<<' ';
//		cout<<endl;
//	}
	for(int i=1;i<=n;i++){
		int cl=col[i];
		if(vs[cl])continue;
		vs[cl]=1;
		fl[cl]=spfa(i,1,scc[cl])|spfa(i,-1,scc[cl]);
//		cout<<i<<' '<<cl<<' '<<fl[cl]<<endl;
	}
	//cout<<"DEBUG"<<endl;
	queue<int>q;
	for(int i=1;i<=cnt;i++)
		if(!in[i])q.push(i);
	while(q.size()){
		int u=q.front();q.pop();
		for(auto v:e[u]){
			fl[v]|=fl[u];
			if(!--in[v])q.push(v);
		}
	}
	while(Q--){
		int x;
		cin>>x;
		x=(x%n+n)%n+1;
		if(fl[col[x]])cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return ;
}
int T=1;

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	cin>>T;
	for(int kase=1;kase<=T;kase++){
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 114288kb

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: 11ms
memory: 113660kb

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: 11ms
memory: 109864kb

input:

1 1 1
0 1000000000
-1000000000

output:

Yes

result:

ok "Yes"

Test #4:

score: 0
Accepted
time: 4ms
memory: 111100kb

input:

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

output:

No
No
No

result:

ok 3 tokens

Test #5:

score: 0
Accepted
time: 190ms
memory: 144240kb

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:

No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
No
...

result:

ok 500000 tokens

Test #6:

score: -100
Time Limit Exceeded

input:

100848 500000 500000
720352587 361776806
231853504 -933882325
960971230 -83519300
-152772415 -631132247
842871215 -666621297
857194330 -754943024
-698506963 -705416545
-3551931 -927937446
628710320 -942247987
674921043 847145884
-325629529 475694308
-339363446 686789318
236702996 654762989
420412365...

output:


result: