QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788666#9810. Obliviate, Then ReincarnatecrychicWA 3ms8880kbC++201.7kb2024-11-27 17:49:182024-11-27 17:49:26

Judging History

This is the latest submission verdict.

  • [2024-11-27 17:49:26]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 8880kb
  • [2024-11-27 17:49:18]
  • Submitted

answer

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=5e5+5;
vector<pii>e[maxn];
int dfn[maxn],low[maxn],cnt;
int inst[maxn],scc[maxn],sc;
int fl[maxn],ans[maxn];
vector<int>ins[maxn],stk;
void dfs(int x){
	dfn[x]=low[x]=++cnt;
	inst[x]=1;
	stk.push_back(x);
	for(auto t:e[x]){
		int u=t.first;
		if(!dfn[u]){
			dfs(u);
			low[x]=min(low[x],low[u]);
		}
		else if(inst[u])low[x]=min(low[x],dfn[u]);
	}
	if(low[x]==dfn[x]){
		sc++;
		while(1){
			int u=stk.back();
			inst[u]=0;
			scc[u]=sc;
			ins[sc].push_back(u);
			stk.pop_back();
			if(u==x)break;
		}
	}
}
ll dis[maxn];
int vis[maxn],T;
void dfs2(int x){
	vis[x]=1;
	for(auto t:e[x]){
		int u=t.first,w=t.second;
		if(scc[u]!=scc[x])continue;
		if(vis[u]){
			if(dis[u]!=dis[x]+w)fl[T]=1;
			continue;
		}
		dis[u]=dis[x]+w;
		dfs2(u);
	}
}
void dfs3(int x){
	if(vis[x])return;
	vis[x]=1;
	for(auto t:e[x]){
		int u=t.first;
		dfs3(u);
		ans[x]|=ans[u];
	}
}
void solve(){
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>w;
		u=(u%n+n)%n+1;
		v=((u+w)%n+n)%n+1;
		e[u].push_back({v,w});
		// cout<<u<<" "<<v<<" "<<w<<"\n";
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			dfs(i);
		}
	}
	for(int i=1;i<=sc;i++){
		T=i;
		dfs2(ins[i][0]);
		if(fl[i]){
			for(auto u:ins[i]){
				ans[u]=1;
			}
		}
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		dfs3(i);
	}
	for(int i=1;i<=q;i++){
		int x;
		cin>>x;
		x=(x%n+n)%n+1;
		if(ans[x])cout<<"Yes\n";
		else cout<<"No\n";
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	// cin>>t;
	while(t--)solve();
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 8880kb

input:

3 2 3
1 1
-1 3
1
2
3

output:

No
No
No

result:

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