QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#783078#9810. Obliviate, Then ReincarnateFHQY#Compile Error//C++172.7kb2024-11-25 23:12:562024-11-25 23:12:57

Judging History

This is the latest submission verdict.

  • [2024-11-26 23:19:26]
  • hack成功,自动添加数据
  • (/hack/1260)
  • [2024-11-25 23:12:57]
  • Judged
  • [2024-11-25 23:12:56]
  • 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=5e5+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]>=g.size()*2) 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

answer.code: In function ‘bool spfa(long long int, long long int, std::vector<long long int>)’:
answer.code:61:49: error: request for member ‘size’ in ‘g’, which is of non-class type ‘std::vector<std::pair<long long int, long long int> > [500005]’
   61 |                                 if(cntt[now]>=g.size()*2) return true;
      |                                                 ^~~~