QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #151640 | #4924. 蜘蛛爬树 | zhouhuanyi | Compile Error | / | / | C++14 | 5.6kb | 2023-08-27 12:15:10 | 2023-08-27 12:15:14 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 400000
#define M 60
using namespace std;
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
const int inf=(int)(1e9);
struct reads
{
int num,snum;
long long data;
};
struct points
{
int x;
long long y;
};
int n,m,q,leng,length,rt,fa[N+1],a[N+1],depth[N+1],smz,sz[N+1],sx,sy,sd,sw;
long long dis[N+1][M+1];
vector<reads>E[N+1];
vector<reads>ES[N+1];
vector<int>v[M+1][N+1];
bool used[N+1],vis[N+1];
void add(int x,int y,int z,long long w)
{
E[x].push_back((reads){y,z,w}),E[y].push_back((reads){x,z,w});
return;
}
void add2(int x,int y,long long z)
{
ES[x].push_back((reads){y,++leng,z}),ES[y].push_back((reads){x,++leng,z});
return;
}
bool cmp(int x,int y)
{
return a[x]<a[y];
}
void dfs(int x)
{
int nw=0,d=0;
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].num])
{
dfs(E[x][i].num);
if (!nw) nw=E[x][i].num,d=E[x][i].data;
else ++length,add2(length,nw,0),add2(length,E[x][i].num,E[x][i].data),nw=length,d=0;
}
if (nw) add2(x,nw,d);
return;
}
void get_rt(int x)
{
vis[x]=sz[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].snum]&&!vis[E[x][i].num])
{
get_rt(E[x][i].num),sz[x]+=sz[E[x][i].num];
if (max(sz[E[x][i].num],smz-sz[E[x][i].num])<minn) minn=max(sz[E[x][i].num],smz-sz[E[x][i].num]),sx=x,sy=E[x][i].num,sd=E[x][i].snum,sw=E[x][i].data;
}
vis[x]=0;
return;
}
void dfs2(int x,int d)
{
vis[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i].snum]&&!vis[E[x][i].num])
dis[E[x][i].num][d]=dis[x][d]+E[x][i].data,dfs2(E[x][i].num);
vis[x]=0;
return;
}
int solve(int x,int szt,int d)
{
depth[x]=d,smz=szt,minn=inf,get_rt(x);
if (minn==inf) return x;
int nw=++length;
used[sd]=1,dfs2(sx,d),dis[sy][d]=sw,dfs2(sy,d),ls[nw]=solve(sx,szt-sz[sx],d+1),rs[nw]=solve(sy,sz[sy],d+1),fa[ls[nw]]=fa[rs[nw]]=nw;
return;
}
points operator + (points a,points b)
{
return (points){a.x+b.x,a.y+b.y};
}
points operator - (points a,points b)
{
return (points){a.x-b.x,a.y-b.y};
}
long long operator * (points a,points b)
{
return 1ll*a.x*b.y-1ll*a.y*b.x;
}
bool check(points a,points b,points c)
{
return (b-a)*(c-a)<=0;
}
int lca(int x,int y)
{
if (depth[x]<depth[y]) swap(x,y);
while (depth[x]!=depth[y]) x=fa[x];
while (x!=y) x=fa[x],y=fa[y];
return x;
}
int main()
{
int x,y,sx,tx,d1,d2,d,sd,ps;
point ds;
long long z,s,t;
length=n=read(),m=read(),q=read();
for (int i=1;i<=n;++i) a[i]=read(),p[i]=i;
sort(p+1,p+n+1,cmp);
for (int i=1;i<=n-1;++i) x=read(),y=read(),z=read(),add(x,y,z,i);
dfs(1);
for (int i=1;i<=n;++i) used[i]=0;
rt=solve(1,1);
for (int i=1;i<=n;++i)
{
x=p[i];
for (int j=depth[x];j>=2;--j)
{
for (int k=1;k<=j-1;++k)
{
ds=(points){a[p[i]],dis[p[i]][j-1]+dis[p[i]][k]};
while (v[k][x].size()>=2&&check(v[k][x][(int)(v[k][x].size())-2],v[k][x].back(),ds)) v[k][x].pop_back();
v[k][x].push_back(ds);
}
x=fa[x];
}
}
for (int i=1;i<=q;++i)
{
s=read(),t=read(),d1=(s-1)/n+1,d2=(t-1)/n+1,x=s-(d1-1)*n,y=t-(d2-1)*n,sd=abs(d1-d2),sx=l=lca(s,t),ans=dis[s][depth[l]]+dis[t][depth[l]]+1ll*min(a[x],a[y])*d;
for (int j=depth[l];j>=2;--j)
{
if (ls[fa[sx]]==sx)
{
d=depth[rs[fa[sx]]],tx=rs[fa[sx]],ps=0;
for (int k=lg[v[d][tx].size()];k>=0;--k)
if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
ps+=(1<<k);
ans=min(ans,1ll*v[d][tx][ps].x*sd+v[d][tx][ps].y+dis[x][j-1]+dis[y][j-1]);
}
else
{
d=depth[ls[fa[sx]]],tx=ls[fa[sx]],sx=0;
for (int k=lg[v[d][tx].size()];k>=0;--k)
if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
ps+=(1<<k);
ans=min(ans,1ll*v[d][tx][ps].x*sd+v[d][tx][ps].y+dis[x][j-1]+dis[y][j-1]);
}
sx=fa[sx];
}
sx=x;
for (int j=depth[x];j>=depth[l]+2;--j)
{
if (ls[fa[sx]]==sx)
{
d=depth[l],tx=rs[fa[sx]],ps=0;
for (int k=lg[v[d][tx].size()];k>=0;--k)
if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
ps+=(1<<k);
ans=min(ans,1ll*v[d][tx][ps].x*sd+v[d][tx][ps].y+dis[x][j-1]+dis[y][l]);
}
else
{
d=depth[l],tx=ls[fa[sx]],sx=0;
for (int k=lg[v[d][tx].size()];k>=0;--k)
if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
ps+=(1<<k);
ans=min(ans,1ll*v[d][tx][ps].x*sd+v[d][tx][ps].y+dis[x][j-1]+dis[y][l]);
}
sx=fa[sx];
}
sx=y;
for (int j=depth[y];j>=depth[l]+2;--j)
{
if (ls[fa[sx]]==sx)
{
d=depth[l],tx=rs[fa[sx]],ps=0;
for (int k=lg[v[d][tx].size()];k>=0;--k)
if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
ps+=(1<<k);
ans=min(ans,1ll*v[d][tx][ps].x*sd+v[d][tx][ps].y+dis[x][l]+dis[y][j-1]);
}
else
{
d=depth[l],tx=ls[fa[sx]],sx=0;
for (int k=lg[v[d][tx].size()];k>=0;--k)
if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
ps+=(1<<k);
ans=min(ans,1ll*v[d][tx][ps].x*sd+v[d][tx][ps].y+dis[x][l]+dis[y][j-1]);
}
sx=fa[sx];
}
printf("%lld\n",ans);
}
return 0;
}
Details
answer.code: In function ‘void get_rt(int)’:
answer.code:67:70: error: ‘minn’ was not declared in this scope
67 | if (max(sz[E[x][i].num],smz-sz[E[x][i].num])<minn) minn=max(sz[E[x][i].num],smz-sz[E[x][i].num]),sx=x,sy=E[x][i].num,sd=E[x][i].snum,sw=E[x][i].data;
| ^~~~
answer.code: In function ‘void dfs2(int, int)’:
answer.code:77:72: error: too few arguments to function ‘void dfs2(int, int)’
77 | dis[E[x][i].num][d]=dis[x][d]+E[x][i].data,dfs2(E[x][i].num);
| ~~~~^~~~~~~~~~~~~
answer.code:72:6: note: declared here
72 | void dfs2(int x,int d)
| ^~~~
answer.code: In function ‘int solve(int, int, int)’:
answer.code:83:28: error: ‘minn’ was not declared in this scope
83 | depth[x]=d,smz=szt,minn=inf,get_rt(x);
| ^~~~
answer.code:86:56: error: ‘ls’ was not declared in this scope
86 | used[sd]=1,dfs2(sx,d),dis[sy][d]=sw,dfs2(sy,d),ls[nw]=solve(sx,szt-sz[sx],d+1),rs[nw]=solve(sy,sz[sy],d+1),fa[ls[nw]]=fa[rs[nw]]=nw;
| ^~
answer.code:86:88: error: ‘rs’ was not declared in this scope; did you mean ‘rt’?
86 | used[sd]=1,dfs2(sx,d),dis[sy][d]=sw,dfs2(sy,d),ls[nw]=solve(sx,szt-sz[sx],d+1),rs[nw]=solve(sy,sz[sy],d+1),fa[ls[nw]]=fa[rs[nw]]=nw;
| ^~
| rt
answer.code:87:9: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
87 | return;
| ^~~~~~
answer.code: In function ‘int main()’:
answer.code:115:9: error: ‘point’ was not declared in this scope; did you mean ‘points’?
115 | point ds;
| ^~~~~
| points
answer.code:118:44: error: ‘p’ was not declared in this scope
118 | for (int i=1;i<=n;++i) a[i]=read(),p[i]=i;
| ^
answer.code:119:14: error: ‘p’ was not declared in this scope
119 | sort(p+1,p+n+1,cmp);
| ^
answer.code:119:9: error: ‘sort’ was not declared in this scope; did you mean ‘short’?
119 | sort(p+1,p+n+1,cmp);
| ^~~~
| short
answer.code:123:17: error: too few arguments to function ‘int solve(int, int, int)’
123 | rt=solve(1,1);
| ~~~~~^~~~~
answer.code:81:5: note: declared here
81 | int solve(int x,int szt,int d)
| ^~~~~
answer.code:131:33: error: ‘ds’ was not declared in this scope; did you mean ‘s’?
131 | ds=(points){a[p[i]],dis[p[i]][j-1]+dis[p[i]][k]};
| ^~
| s
answer.code:140:104: error: ‘l’ was not declared in this scope
140 | s=read(),t=read(),d1=(s-1)/n+1,d2=(t-1)/n+1,x=s-(d1-1)*n,y=t-(d2-1)*n,sd=abs(d1-d2),sx=l=lca(s,t),ans=dis[s][depth[l]]+dis[t][depth[l]]+1ll*min(a[x],a[y])*d;
| ^
answer.code:140:115: error: ‘ans’ was not declared in this scope; did you mean ‘abs’?
140 | s=read(),t=read(),d1=(s-1)/n+1,d2=(t-1)/n+1,x=s-(d1-1)*n,y=t-(d2-1)*n,sd=abs(d1-d2),sx=l=lca(s,t),ans=dis[s][depth[l]]+dis[t][depth[l]]+1ll*min(a[x],a[y])*d;
| ^~~
| abs
answer.code:143:29: error: ‘ls’ was not declared in this scope; did you mean ‘s’?
143 | if (ls[fa[sx]]==sx)
| ^~
| s
answer.code:145:41: error: ‘rs’ was not declared in this scope; did you mean ‘s’?
145 | d=depth[rs[fa[sx]]],tx=rs[fa[sx]],ps=0;
| ^~
| s
answer.code:146:44: error: ‘lg’ was not declared in this scope
146 | for (int k=lg[v[d][tx].size()];k>=0;--k)
| ^~
answer.code:147:96: error: request for member ‘x’ in ‘v[d][tx].std::vector<int>::operator[](((std::vector<int>::size_type)(ps + (1 << k))))’, which is of non-class type ‘__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type’ {aka ‘int’}
147 | if (ps+(1<<k)<v[d][tx].size()&&1ll*v[d][tx][ps+(1<<k)].x*sd+v[d][tx][ps+(1<<k)].y<1ll*v[d][tx][ps+(1<<k)-1].x*sd+v[d][tx][ps+(1<<k)-1].y)
| ...