QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#789036#9810. Obliviate, Then Reincarnateucup-team4352Compile Error//Python31.9kb2024-11-27 19:07:062024-11-27 19:07:07

Judging History

This is the latest submission verdict.

  • [2024-11-27 19:07:07]
  • Judged
  • [2024-11-27 19:07:06]
  • 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];
vector<int>ed[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);
	}
}
int deg[maxn];
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-1)%n+1;
		v=((u+w)%n+n-1)%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]);
	}
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		for(auto t:e[i]){
			int u=t.first;
			if(scc[u]!=scc[i]){
				ed[scc[u]].push_back(scc[i]);
				deg[scc[i]]++;
			}
		}
	}
	queue<int>qu;
	for(int i=1;i<=sc;i++){
		if(deg[i]==0)qu.push(i);
	}
	while(!qu.empty()){
		int x=qu.front();
		qu.pop();
		for(auto u:ed[x]){
			deg[u]--;
			fl[u]|=fl[x];
			if(deg[u]==0){
				qu.push(u);
			}
		}
	}
	for(int i=1;i<=q;i++){
		int x;
		cin>>x;
		x=(x%n+n-1)%n+1;
		if(fl[scc[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;
}

Details

  File "answer.code", line 4
    using namespace std;
          ^^^^^^^^^
SyntaxError: invalid syntax