社区讨论
空间限制是否应该放宽一些?
P3379【模板】最近公共祖先(LCA)参与者 4已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @mi5hosl5
- 此快照首次捕获于
- 2025/11/19 12:15 4 个月前
- 此快照最后确认于
- 2025/11/19 12:15 4 个月前
我用边表存树,感觉没有什么地方内存浪费,可是手算内存达到181M,想用vector,看见这么多帖子上说vector会超时,也就不敢用了......难道空间限制不能放宽一点吗?今年NOIP提高组的空间限制是到512M的吧
代码如下
CPP#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<utility>
using namespace std;
const int maxn=500000+10;
int heade[maxn],ev[2*maxn],nexte[2*maxn],isvis[maxn];
int ver[2*maxn],a[2*maxn],first[maxn],rmq[2*maxn][21],pos[2*maxn][21];
int n,m,s,tot=0,num=1;
void add(int u,int v)
{
tot++;ev[tot]=v;
nexte[tot]=heade[u];
heade[u]=tot;
}
void dfs(int u,int cur)
{
int i,j,ui;
ver[num]=u;a[num]=cur;isvis[u]=1;
if(!first[u]){first[u]=num;}
num++;
for(i=heade[u];i!=-1;i=nexte[i])
{
ui=ev[i];
if(!isvis[ui])
{
dfs(ui,cur+1);
ver[num]=u;a[num]=cur;
num++;
}
}
}
void rmq_list()
{
int i,j,m;
m=(int)(log(num)/log(2));
for(i=1;i<=num;i++){rmq[i][0]=a[i];pos[i][0]=i;}
for(j=1;j<=m;j++)
{
for(i=1;i+(1<<j)-1<=num;i++)
{
if(rmq[i][j-1]<rmq[i+(1<<(j-1))][j-1])
{
rmq[i][j]=rmq[i][j-1];
pos[i][j]=pos[i][j-1];
}
else
{
rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
pos[i][j]=pos[i+(1<<(j-1))][j-1];
}
}
}
}
void rmq_query(int x,int y)
{
int i,j,m,p;
m=(int)(log(y-x+1)/log(2));
if(rmq[x][m]<rmq[y-(1<<m)+1][m])
{
p=pos[x][m];
printf("%d\n",ver[p]);
}
else
{
p=pos[y-(1<<m)+1][m];
printf("%d\n",ver[p]);
}
}
void lca(int u,int v)
{
int x,y;
x=first[u];y=first[v];
if(x>y){swap(x,y);}
rmq_query(x,y);
}
int main()
{
int i,j,u,v;
cin>>n>>m>>s;
memset(heade,-1,sizeof(heade));
memset(nexte,-1,sizeof(nexte));
memset(first,0,sizeof(first));
memset(a,127,sizeof(a));
for(i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(s,1);num--;
rmq_list();
for(i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
lca(u,v);
}
return 0;
}
回复
共 5 条回复,欢迎继续交流。
正在加载回复...