社区讨论

空间限制是否应该放宽一些?

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 条回复,欢迎继续交流。

正在加载回复...