QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#388700#5828. 游戏Ecec243Compile Error//C++233.5kb2024-04-13 18:20:312024-04-13 18:20:32

Judging History

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

  • [2024-04-13 18:20:32]
  • 评测
  • [2024-04-13 18:20:31]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+7;
struct edge
{
	int y,next;
}e[2*N];
int link[N],t=0;
void add(int x,int y)
{
	e[++t].y=y;
	e[t].next=link[x];
	link[x]=t;
}
namespace tree
{
	int dep[N],st[2*N][20],tot=0;
	int lg[2*N],dfn[N];
	void dfs(int x,int pre)
	{
		st[++tot][0]=x;
		dfn[x]=tot;
		for(int i=link[x];i;i=e[i].next)
		{
			int y=e[i].y;
			if(y==pre)continue;
			dep[y]=dep[x]+1;
			dfs(y,x);
			st[++tot][0]=x; 
		}
	}
	inline int Min(int x,int y)
	{
		return dep[x]<dep[y]?x:y;
	}
	void Build()
	{
		dfs(1,0);
		for(int i=2;i<=tot;i++)lg[i]=lg[i>>1]+1;
		for(int k=1;k<=lg[tot];k++)
		for(int i=1;i+(1<<k)-1<=tot;i++)
		st[i][k]=Min(st[i][k-1],st[i+(1<<(k-1))][k-1]);
	}
	inline int LCA(int x,int y)
	{
		x=dfn[x];y=dfn[y];
		if(x>y)swap(x,y);
		int k=lg[y-x+1];
		return Min(st[x][k],st[y-(1<<k)+1][k]);
	}
	inline int dist(int x,int y)
	{
		return dep[x]+dep[y]-2*dep[LCA(x,y)];
	}
}
int st,ed;
int n,m;
int A[N],B[N],fa[N];
void dfs(int x,int pre,int *D)
{
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(y==pre)continue;
		fa[y]=x;
		D[y]=D[x]+1;
		dfs(y,x,D);
	}
}
bool ins[N];
int seq[N];
int h[N];
void dfs2(int x,int pre)
{
	h[x]=0;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(ins[y]||y==pre)continue;
		dfs2(y,x);
		h[x]=max(h[x],h[y]+1);
	}
}
int qoj[N],dfn[N];
int cnt=0;
void dfs3(int x,int pre)
{
	qoj[++cnt]=x;
	dfn[x]=cnt;
	for(int i=link[x];i;i=e[i].next)
	{
		int y=e[i].y;
		if(ins[y]||y==pre)continue;
		if(h[x]==h[y]+1)
		{
			dfs3(y,x);
			return;
		}
	}
}
int mx[N][20];
int lg[N];
inline int Max(int x,int y){return h[x]>h[y]?x:y;}
int x,y,z;
int query(int l,int r)
{
	int k=lg[r-l+1];
	return Max(mx[l][k],mx[r-(1<<k)+1][k]);
}
int dft[N];
bool check(int a,int b,int c)
{
	if(b==0) 
	{
		x=seq[1];
		y=seq[a+1];
		z=seq[a+c+1];
		return 1;
	}
	int l=a+1,r=m-c;
	if(l>r)return 0;
	int o=query(l,r);
	if(h[o]<b)return 0;
	x=seq[dft[o]-a];
	y=qoj[dfn[o]+b];
	z=seq[dft[o]+c];
	return 1;
}
bool check(int x,int y,int z,int u,int v,int w)
{
	if(tree::dist(x,y)!=u)return 0;
	if(tree::dist(x,z)!=v)return 0;
	if(tree::dist(z,y)!=w)return 0;
	return 1;
}
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		add(u,v);
		add(v,u);
	}
	tree::Build();
	dfs(1,0,A);
	for(int i=1;i<=n;i++)
	if(A[i]>A[st])st=i;
	fa[st]=0;
	dfs(st,0,B);
	for(int i=1;i<=n;i++)
	if(B[i]>B[ed])ed=i;
	int o=ed;
	while(o)
	{
		ins[o]=1;
		seq[++m]=o;
		dft[o]=m;
		o=fa[o];
	}
	for(int i=1;i<=m;i++)
	{
		dfs2(seq[i],0);
		dfs3(seq[i],0);
		mx[i][0]=seq[i];
	}
	for(int i=2;i<=m;i++)lg[i]=lg[i>>1]+1;
	for(int k=1;k<=lg[m];k++)
	for(int i=1;i+(1<<k)-1<=m;i++)
	mx[i][k]=Max(mx[i][k-1],mx[i+(1<<(k-1))][k-1]); 
	int q;
	cin>>q;
	while(q--)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		int u=a,v=b,w=c;
		bool flag=0;
		int d=(a+b+c)/2;
		a=d-a;b=d-b;c=d-c;
		if(!flag)flag|=check(a,b,c);
		if(!flag)flag|=check(a,c,b);
		if(!flag)flag|=check(b,a,c);
		if(!flag)flag|=check(b,c,a);
		if(!flag)flag|=check(c,a,b);
		if(!flag)flag|=check(c,b,a);
		if(check(x,y,z,u,v,w))printf("%d %d %d\n",x,y,z);
		else if(check(x,z,y,u,v,w))printf("%d %d %d\n",x,z,y);
		else if(check(y,x,z,u,v,w))printf("%d %d %d\n",y,x,z);
		else if(check(y,z,x,u,v,w))printf("%d %d %d\n",y,z,x);
		else if(check(z,x,y,u,v,w))printf("%d %d %d\n",z,x,y);
		else if(check(z,y,x,u,v,w))printf("%d %d %d\n",z,y,x);
		else printf("-1\n");
	}
	return 0;
}

詳細信息

answer.code:8:11: error: ‘int link [200007]’ redeclared as different kind of entity
    8 | int link[N],t=0;
      |           ^
In file included from /usr/include/c++/13/bits/atomic_wait.h:44,
                 from /usr/include/c++/13/bits/atomic_base.h:42,
                 from /usr/include/c++/13/bits/shared_ptr_atomic.h:33,
                 from /usr/include/c++/13/memory:81,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:56,
                 from answer.code:1:
/usr/include/unistd.h:789:12: note: previous declaration ‘int link(const char*, const char*)’
  789 | extern int link (const char *__from, const char *__to)
      |            ^~~~
answer.code: In function ‘void add(int, int)’:
answer.code:12:25: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   12 |         e[t].next=link[x];
      |                         ^
answer.code:12:25: error: invalid conversion from ‘int (*)(const char*, const char*) noexcept’ to ‘int’ [-fpermissive]
   12 |         e[t].next=link[x];
      |                   ~~~~~~^
      |                         |
      |                         int (*)(const char*, const char*) noexcept
answer.code:13:15: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   13 |         link[x]=t;
      |               ^
answer.code:13:16: error: assignment of read-only location ‘*(link + ((sizetype)x))’
   13 |         link[x]=t;
      |         ~~~~~~~^~
answer.code: In function ‘void tree::dfs(int, int)’:
answer.code:23:33: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   23 |                 for(int i=link[x];i;i=e[i].next)
      |                                 ^
answer.code:23:33: error: invalid conversion from ‘int (*)(const char*, const char*) noexcept’ to ‘int’ [-fpermissive]
   23 |                 for(int i=link[x];i;i=e[i].next)
      |                                 ^
      |                                 |
      |                                 int (*)(const char*, const char*) noexcept
answer.code: In function ‘void dfs(int, int, int*)’:
answer.code:61:25: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   61 |         for(int i=link[x];i;i=e[i].next)
      |                         ^
answer.code:61:25: error: invalid conversion from ‘int (*)(const char*, const char*) noexcept’ to ‘int’ [-fpermissive]
   61 |         for(int i=link[x];i;i=e[i].next)
      |                         ^
      |                         |
      |                         int (*)(const char*, const char*) noexcept
answer.code: In function ‘void dfs2(int, int)’:
answer.code:76:25: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   76 |         for(int i=link[x];i;i=e[i].next)
      |                         ^
answer.code:76:25: error: invalid conversion from ‘int (*)(const char*, const char*) noexcept’ to ‘int’ [-fpermissive]
   76 |         for(int i=link[x];i;i=e[i].next)
      |                         ^
      |                         |
      |                         int (*)(const char*, const char*) noexcept
answer.code: In function ‘void dfs3(int, int)’:
answer.code:90:25: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   90 |         for(int i=link[x];i;i=e[i].next)
      |                         ^
answer.code:90:25: error: invalid conversion from ‘int (*)(const char*, const char*) noexcept’ to ‘int’ [-fpermissive]
   90 |         for(int i=link[x];i;i=e[i].next)
      |                         ^
      |                         |
      |                         int (*)(const char*, const char*) noexcept
answer.code: In function ‘int main()’:
answer.code:142:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  142 |                 scanf("%d %d",&u,&v);
      |                 ~~~~~^~~~~~~~~~~~~~~
answer.code:177:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  177 |                 scanf("%d %d %d",&a,&b,&c);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~