QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#785296#9810. Obliviate, Then Reincarnatec201904WA 8ms47540kbC++142.7kb2024-11-26 17:26:222024-11-26 17:26:23

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-26 17:26:23]
  • Judged
  • Verdict: WA
  • Time: 8ms
  • Memory: 47540kb
  • [2024-11-26 17:26:22]
  • Submitted

answer

//This program need not to be initialized(Write this for all programs)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=5e5+5;
int n,m,q;//number of floors,relocation instructions(edges),queries
int flr=0;//number of floors that appear
map<int,int>h;//mapping
struct node{
	int v;
	ll d;
};
vector<node>e[N];//edges
vector<int>e_opp[N];
void addedge(int x,int d){//x floor add d
	if(!d)return ;
	x=(x%n+n)%n;
	int y=x+d;y=(y%n+n)%n;
	if(!h[x]){
		//cout<<x<<" ";
		h[x]=++flr;
		x=flr;
		//cout<<"why 1?"<<endl;
	}
	if(!h[y]){
		h[y]=++flr;
		y=flr;
	}
	//cout<<x<<" "<<y<<" "<<d<<endl;
	e[x].push_back((node){y,d});
	e_opp[y].push_back(x);	
	//if(x==y)tag[x]=1; 
	return ;
}
int pts=0;//
int low[N],dfn[N],top[N],tops;
vector<int>scc[N];//strong connected component
int vis[N];
ll pe[N];//potential energy;   
void dfs(int u,int tp){//tp means top
	vis[u]=1;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i].v;
		if(vis[v])continue;
		if(top[v]!=tp)continue;
		pe[v]=pe[u]+e[u][i].d;
	}
	return ;
}
int judge(int tp){//only consider pts in the scc
	dfs(scc[tp][0],tp);
	int sz=scc[tp].size();
	for(int i=0;i<sz;i++){
		int u=scc[tp][i];
		for(int j=0;j<e[u].size();j++){
			int v=e[u][j].v;;
			if(top[v]!=tp)continue;
			int d=e[u][j].d;
			
			if(pe[v]!=(pe[u]+d))return 1; 
		}
	}
	return 0;
}
stack<int>st;
int tag[N];//is it in a non-zero scc?
void tarjan(int u){
	st.push(u);
	low[u]=dfn[u]=++pts;top[u]=0;//initialize
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
			//there suppose to be if !top[v],but this doesn't change the result 
		}
		else if(!top[v]){//!top[v] means that v is in stack
			low[u]=min(low[u],dfn[v]);//why ?
		}
	} 
	if(low[u]==dfn[u]){
		top[u]=++tops;
		scc[tops].push_back(u);
		while(st.top()!=u){
			int x=st.top();st.pop();
			top[x]=tops;	
			scc[tops].push_back(x);
		}
		st.pop();
		if(judge(tops)){
			//cout<<u<<" "<<scc[tops].size()<<endl; 
			for(int i=0;i<scc[tops].size();i++){
				int x=scc[tops][i];
				tag[x]=1;//try not to use too long sentences.
			}
		}
	}
}
void run_opp(int u){
	//if(tag[u])return ; (initial points should not be deleted)
	for(int i=0;i<e_opp[u].size();i++){
		int v=e_opp[u][i];
		if(tag[v])return ;
		tag[v]=1;
		run_opp(v);
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&q);
	int a,b;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b); 
		addedge(a,b);
	}
	for(int i=1;i<=flr;i++){
		if(!low[i])tarjan(i);
	}
	for(int i=1;i<=flr;i++){
		if(tag[i])run_opp(i);
	}
	while(q--){
		int x;
		scanf("%d",&x);
		x=(x%n+n)%n;
		if(tag[vis[x]])puts("Yes");
		else puts("No");
	}
	return 0;
}
 

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 47244kb

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: 5ms
memory: 47540kb

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: 8ms
memory: 47256kb

input:

1 1 1
0 1000000000
-1000000000

output:

No

result:

wrong answer 1st words differ - expected: 'Yes', found: 'No'