BZOJ 5165 树上倍增

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=5165

题意：见原题面。

树上多点 lca 为其中 dfn 最大/最小值的 lca。

丧心病狂卡 log.... 好像还是我第一次写 tarjan...

#include <cmath>
#include <queue>
#include <cstdio>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 3000010
#define Q 1010
#define ll long long
#define inf 1000000010
using namespace std;
#define fstc __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline))
char xB[1<<15],*xS=xB,*xT=xB;
#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
#define OUT 10000000
char Out[OUT],*ou=Out;
int Outn[30],Outcnt;
fstc IL void write(int x)
{
    if(!x)*ou++=48;
    else
    {
        for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;
        while(Outcnt)*ou++=Outn[Outcnt--];
    }
}
fstc IL int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n=1,m;
int dfn[N];
struct zgz
{
    int next,to;
}edge[N];
int head[N],cnt=1;
vector<pair<int,int> > p[N];
fstc void add(int from,int to)
{
    edge[cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt++;
}
int q[Q][Q],len[Q],top;
int ans[N],tim;
fstc void dfs_n(int x)
{
    dfn[x]=++tim;
    for(int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        dfs_n(to);
    }
}
int fa[N],vis[N];
fstc int find(int x)
{return fa[x]==x?x:fa[x]=find(fa[x]);}
fstc void dfs(int x)
{
    fa[x]=x;
    for(int i=head[x];i;i=edge[i].next)
    {
        int to=edge[i].to;
        dfs(to),fa[to]=x;
    }
    vis[x]=1;
    for(int i=0;i<p[x].size();i++)
    if(vis[p[x][i].first])ans[p[x][i].second]=find(p[x][i].first);
}
fstc int main()
{
    m=read();
    while(m--)
    {
        char opt=getchar();
        while(opt!='A'&&opt!='Q')opt=getchar();
        if(opt=='A')
        {
            int x=read();
            add(x,++n);
        }
        else
        {
            int k=read();
            len[++top]=k;
            for(int i=1;i<=k;i++)q[top][i]=read();
        }
    }
    dfs_n(1);
    for(int i=1;i<=top;i++)
    {
        int mn=q[i][1],mx=q[i][1];
        if(len[i]==1)
        {
            ans[i]=q[i][1];
            continue ;
        }
        for(int j=1;j<=len[i];j++)
        {
            if(dfn[q[i][j]]>dfn[mx])mx=q[i][j];
            if(dfn[q[i][j]]<dfn[mn])mn=q[i][j];
        }
        p[mn].push_back(make_pair(mx,i));
        p[mx].push_back(make_pair(mn,i));
    }
    dfs(1);
    for(int i=1;i<=top;i++)write(ans[i]),*ou++='\n';
    fwrite(Out,1,ou-Out,stdout);
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

#include <cmath>

#include <queue>

#include <cstdio>

#include <iomanip>

#include <cstdlib>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 3000010

#define Q 1010

#define ll long long

#define inf 1000000010

using namespace std;

#define fstc __attribute__((optimize("-O3")))

#define IL __inline__ __attribute__((always_inline))

char xB[1<<15],*xS=xB,*xT=xB;

#define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)

#define OUT 10000000

char Out[OUT],*ou=Out;

int Outn[30],Outcnt;

fstc IL void write(int x)

{

if(!x)*ou++=48;

else

{

for(Outcnt=0;x;x/=10)Outn[++Outcnt]=x%10+48;

while(Outcnt)*ou++=Outn[Outcnt--];

}

fstc IL int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n=1,m;

int dfn[N];

struct zgz

{

int next,to;

}edge[N];

int head[N],cnt=1;

vector<pair<int,int> > p[N];

fstc void add(int from,int to)

{

edge[cnt].to=to;

edge[cnt].next=head[from];

head[from]=cnt++;

}

int q[Q][Q],len[Q],top;

int ans[N],tim;

fstc void dfs_n(int x)

{

dfn[x]=++tim;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to;

dfs_n(to);

}

int fa[N],vis[N];

fstc int find(int x)

{return fa[x]==x?x:fa[x]=find(fa[x]);}

fstc void dfs(int x)

{

fa[x]=x;

for(int i=head[x];i;i=edge[i].next)

{

int to=edge[i].to;

dfs(to),fa[to]=x;

}

vis[x]=1;

for(int i=0;i<p[x].size();i++)

if(vis[p[x][i].first])ans[p[x][i].second]=find(p[x][i].first);

}

fstc int main()

{

m=read();

while(m--)

{

char opt=getchar();

while(opt!='A'&&opt!='Q')opt=getchar();

if(opt=='A')

{

int x=read();

add(x,++n);

}

else

{

int k=read();

len[++top]=k;

for(int i=1;i<=k;i++)q[top][i]=read();

}

dfs_n(1);

for(int i=1;i<=top;i++)

{

int mn=q[i][1],mx=q[i][1];

if(len[i]==1)

{

ans[i]=q[i][1];

continue ;

}

for(int j=1;j<=len[i];j++)

{

if(dfn[q[i][j]]>dfn[mx])mx=q[i][j];

if(dfn[q[i][j]]<dfn[mn])mn=q[i][j];

}

p[mn].push_back(make_pair(mx,i));

p[mx].push_back(make_pair(mn,i));

}

dfs(1);

for(int i=1;i<=top;i++)write(ans[i]),*ou++='\n';

fwrite(Out,1,ou-Out,stdout);

}

zgz233

BZOJ 5165 树上倍增

BZOJ 5201 [NEERC2017]Connections

数据结构入门基础

l1ll5

Comments | 2 条评论

Edw 博主

l1ll5 博主

zgz233