QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#263957#7869. 建设终末树zhouhuanyiCompile Error//C++145.5kb2023-11-25 10:42:152023-11-25 10:42:16

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 10:42:16]
  • 评测
  • [2023-11-25 10:42:15]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<vector>
#define N 2000
#define M 16000000
#define K 30000000
#define S 11
#define W 4000000
using namespace std;
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int x,y;
};
reads tong[N+1],st[N+1];
struct node
{
	int v,nxt;
};
node edge[K+1];
int n,m,q,maxn,top,lengt,lengs,lengths,cater,len,depth[N+1],wrt[W+1],dfnt[N+1],sz[N+1],lca[N+1][N+1],lg[N+1],head[M+1],length,leng,cst[N+1],cnt[N+1],a[N+1][N+1],b[N+1],c[N+1],sfa[N+1][N+1],fa[N+1][S+1],A[N+1],B[N+1],dfn[M+1],low[M+1],stk[M+1],belong[M+1],ans[N+1],ST[N+1][N+1][S+1],rt[S+1][W+1],dis[N+1][N+1];
bool usedt[M+1],vis[M+1],cl[N+1];
vector<int>E[N+1];
int F(int x,int y)
{
	return (x-1)*n+y;
}
int find(int k,int x)
{
	if (rt[k][x]==x) return x;
	return rt[k][x]=find(k,rt[k][x]);
}
void unionn(int k,int x,int y)
{
	rt[k][find(k,x)]=find(k,y);
	return;
}
void add(int x,int y)
{
	E[x].push_back(y),E[y].push_back(x);
	return;
}
void add_edge(int x,int y)
{
	edge[++len]=(node){y,head[x]},head[x]=len;
	return;
}
bool LENG(int x,int y)
{
	return dfnt[x]<=dfnt[y]&&dfnt[y]<=dfnt[x]+sz[x]-1;
}
bool LENGS(int x,int y,int z)
{
	return dis[x][y]+dis[y][z]==dis[x][z];
}
void dfs(int x)
{
	dfnt[x]=++lengt,sz[x]=1;
	for (int i=0;i<E[x].size();++i)
		if (!dfnt[E[x][i]])
			depth[E[x][i]]=depth[x]+1,fa[E[x][i]][0]=sfa[E[x][i]][1]=x,dfs(E[x][i]),st[++lengths]=(reads){x,E[x][i]},sz[x]+=sz[E[x][i]];
	return;
}
void dfs2(int x,int y)
{
	if (LENG(x,y)) lca[y][x]=x;
	for (int i=0;i<E[x].size();++i)
		if (fa[E[x][i]][0]==x)
			lca[y][E[x][i]]=lca[y][x],dfs2(E[x][i],y);
	return;
}
void tarjan(int x)
{
	dfn[x]=low[x]=++lengs,usedt[x]=1,stk[++top]=x;
	for (int i=head[x];i>0;i=edge[i].nxt)
	{
		if (!dfn[edge[i].v]) tarjan(edge[i].v),low[x]=min(low[x],low[edge[i].v]);
		else if (usedt[edge[i].v]) low[x]=min(low[x],dfn[edge[i].v]);
	}
	if (dfn[x]==low[x])
	{
		++cater;
		while (stk[top]!=x) belong[stk[top]]=cater,usedt[stk[top]]=0,top--;
		belong[stk[top]]=cater,usedt[stk[top]]=0,top--;
	}
	return;
}
void adder(int d1,int d2,int x,int y)
{
	int z=lca[x][y],d;
	if (x!=z) d=lg[depth[x]-depth[z]],unionn(d,F(d1,x),F(d2,x)),unionn(d,F(d1,sfa[x][depth[x]-depth[z]-(1<<d)]),F(d2,sfa[x][depth[x]-depth[z]-(1<<d)]));
	if (y!=z) d=lg[depth[y]-depth[z]],unionn(d,F(d1,y),F(d2,y)),unionn(d,F(d1,sfa[y][depth[y]-depth[z]-(1<<d)]),F(d2,sfa[y][depth[y]-depth[z]-(1<<d)]));
	return;
}
int main()
{
	int t1,t2,x,y,d;
	bool op;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
	n=read(),m=read(),q=read(),leng=(n*m)<<1;
	for (int i=1;i<=n-1;++i) x=read(),y=read(),add(x,y);
	depth[1]=1,dfs(1);
	for (int i=1;i<=n;++i) maxn=max(maxn,depth[i]);
	for (int i=1;i<=lg[maxn];++i)
		for (int j=1;j<=n;++j)
			fa[j][i]=fa[fa[j][i-1]][i-1];
	for (int i=1;i<=n;++i)
	{
		sfa[i][0]=i;
		for (int j=1;j<=n;++j) sfa[i][j]=fa[sfa[i][j-1]][0];
	}
	for (int i=1;i<=n;++i) dfs2(1,i);
	for (int i=1;i<=n;++i)
		for (int j=1;j<=n;++j)
			dis[i][j]=depth[i]+depth[j]-(depth[lca[i][j]]<<1);
	for (int i=1;i<=m;++i)
	{
		cst[i]=read();
		for (int j=1;j<=cst[i];++j) a[i][j]=read();
	}
	for (int i=0;i<=lg[maxn];++i)
		for (int j=1;j<=n*m;++j)
			rt[i][j]=j;
	for (int i=1;i<=q;++i)
	{
		t1=read();
		for (int j=1;j<=t1;++j) b[j]=read(),cnt[b[j]]=1;
		t2=read();
		for (int j=1;j<=t2;++j) c[j]=read();
		for (int j=2;j<=t1;++j)
		{
			vis[j]=1;
			for (int k=2;k<=j-1;++k)
				if (LENGS(b[1],b[k],b[j]))
					vis[j]=0;
		}
		for (int j=1;j<=t2-1;++j)
			for (int k=2;k<=t1;++k)
				if (vis[k])
					adder(c[j],c[j+1],b[1],b[k]),scnt++;
	}
	for (int i=lg[maxn];i>=1;--i)
		for (int j=1;j<=m;++j)
			for (int k=1;k<=n;++k)
				if (F(j,k)!=find(i,F(j,k)))
				{
					unionn(i-1,F(j,k),find(i,F(j,k)));
					if (fa[k][i-1])
					{
						d=find(i,F(j,k));
						if (fa[(d-1)%n+1][i-1]) unionn(i-1,F(j,fa[k][i-1]),find(i,F((d+n-1)/n,fa[(d-1)%n+1][i-1])));
					}
				}
	for (int i=1;i<=n*m;++i) wrt[i]=find(0,i);
	for (int i=1;i<=m;++i)
	{
		for (int j=1;j<=n;++j) cnt[j]=0;
		for (int j=1;j<=cst[i];++j) cnt[a[i][j]]=1;
		for (int j=1;j<=lengths;++j) cnt[st[j].x]+=cnt[st[j].y];
		for (int j=2;j<=n;++j)
		{
			if (!cnt[j]) add_edge(wrt[F(i,j)],wrt[F(i,j)]+n*m);
			if (cnt[j]==cst[i]) add_edge(wrt[F(i,j)]+n*m,wrt[F(i,j)]);
		}
		for (int j=1;j<=n;++j)
		{
			length=0;
			if (j!=1) tong[++length]=(reads){wrt[F(i,j)]+n*m,wrt[F(i,j)]};
			for (int k=0;k<E[j].size();++k)
				if (fa[E[j][k]][0]==j)
					tong[++length]=(reads){wrt[F(i,E[j][k])],wrt[F(i,E[j][k])]+n*m};
			A[1]=tong[1].y;
			for (int k=2;k<=length;++k) A[k]=++leng,add_edge(A[k],A[k-1]),add_edge(A[k],tong[k].y);
			B[length]=tong[length].y;
			for (int k=length-1;k>=1;--k) B[k]=++leng,add_edge(B[k],B[k+1]),add_edge(B[k],tong[k].y);
			for (int k=1;k<=length;++k)
			{
				if (k!=1) add_edge(tong[k].x,A[k-1]);
				if (k!=length) add_edge(tong[k].x,B[k+1]);
			}
		}
	}
	for (int i=1;i<=leng;++i)
		if (!dfn[i])
			tarjan(i);
	for (int i=1;i<=m;++i)
		for (int j=1;j<=n;++j)
			if (belong[wrt[F(i,j)]]==belong[wrt[F(i,j)]+n*m])
			{
				puts("-1");
				return 0;
			}
	for (int i=1;i<=m;++i)
	{
		for (int j=1;j<=n;++j) cl[j]=belong[wrt[F(i,j)]]>belong[wrt[F(i,j)]+n*m];
	    for (int j=1;j<=n;++j)
		{
			op=1;
			for (int k=0;k<E[j].size();++k)
				if (fa[E[j][k]][0]==j)
					op&=cl[E[j][k]];
			if (j!=1) op&=(!cl[j]);
			if (op) ans[i]=j;
		}
	}
	for (int i=1;i<=m;++i) printf("%d ",ans[i]);
	puts("");
	return 0;
}

Details

answer.code: In function ‘int main()’:
answer.code:147:70: error: ‘scnt’ was not declared in this scope; did you mean ‘cnt’?
  147 |                                         adder(c[j],c[j+1],b[1],b[k]),scnt++;
      |                                                                      ^~~~
      |                                                                      cnt