QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#388700 | #5828. 游戏 | Ecec243 | Compile Error | / | / | C++23 | 3.5kb | 2024-04-13 18:20:31 | 2024-04-13 18:20:32 |
Judging History
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); | ~~~~~^~~~~~~~~~~~~~~~~~~~~