好家伙,\(unordered\_map\)一直有一两个点超时,换成数组就过了,看来\(STL\)实现的哈希表还是没数组快啊。
向上标记法。
const int N=10010;
int fa[N];
unordered_map<int,int> pos;
int pre[N],in[N];
bool vis[N];
int n,m;
int build(int prel,int prer,int inl,int inr)
{
if(prel > prer) return -1;
int root=pre[prel];
int k=pos[root];
int leftLen=k-inl;
int lchild=build(prel+1,prel+leftLen,inl,k-1);
int rchild=build(prel+leftLen+1,prer,k+1,inr);
if(~lchild) fa[lchild]=k;
if(~rchild) fa[rchild]=k;
return k;
}
int LCA(int u,int v)
{
memset(vis,0,sizeof vis);
vis[u]=true;
while(fa[u])
{
u=fa[u];
vis[u]=true;
}
while(!vis[v]) v=fa[v];
return v;
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>pre[i];
in[i]=pre[i];
}
sort(in+1,in+n+1);
for(int i=1;i<=n;i++)
pos[in[i]]=i;
build(1,n,1,n);
while(m--)
{
int u,v;
cin>>u>>v;
if(pos.count(u) == 0 && pos.count(v) == 0)
printf("ERROR: %d and %d are not found.",u,v);
else if(pos.count(u) == 0)
printf("ERROR: %d is not found.",u);
else if(pos.count(v) == 0)
printf("ERROR: %d is not found.",v);
else
{
u=pos[u],v=pos[v];
int lca=LCA(u,v);
if(lca != u && lca != v)
printf("LCA of %d and %d is %d.",in[u],in[v],in[lca]);
else if(lca == u)
printf("%d is an ancestor of %d.",in[u],in[v]);
else
printf("%d is an ancestor of %d.",in[v],in[u]);
}
puts("");
}
//system("pause");
return 0;
}
同步前进法。
const int N=10010;
int fa[N];
unordered_map<int,int> pos;
int pre[N],in[N];
int dep[N];
int n,m;
int build(int prel,int prer,int inl,int inr,int d)
{
if(prel > prer) return -1;
int root=pre[prel];
int k=pos[root];
dep[k]=d;
int leftLen=k-inl;
int lchild=build(prel+1,prel+leftLen,inl,k-1,d+1);
int rchild=build(prel+leftLen+1,prer,k+1,inr,d+1);
if(~lchild) fa[lchild]=k;
if(~rchild) fa[rchild]=k;
return k;
}
int LCA(int u,int v)
{
if(dep[u] < dep[v]) swap(u,v);
while(dep[u] != dep[v]) u=fa[u];
if(u == v) return v;
while(fa[u] != fa[v])
{
u=fa[u];
v=fa[v];
}
return fa[u];
}
int main()
{
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>pre[i];
in[i]=pre[i];
}
sort(in+1,in+n+1);
for(int i=1;i<=n;i++)
pos[in[i]]=i;
build(1,n,1,n,1);
while(m--)
{
int u,v;
cin>>u>>v;
if(pos.count(u) == 0 && pos.count(v) == 0)
printf("ERROR: %d and %d are not found.",u,v);
else if(pos.count(u) == 0)
printf("ERROR: %d is not found.",u);
else if(pos.count(v) == 0)
printf("ERROR: %d is not found.",v);
else
{
u=pos[u],v=pos[v];
int lca=LCA(u,v);
if(lca != u && lca != v)
printf("LCA of %d and %d is %d.",in[u],in[v],in[lca]);
else if(lca == u)
printf("%d is an ancestor of %d.",in[u],in[v]);
else
printf("%d is an ancestor of %d.",in[v],in[u]);
}
puts("");
}
//system("pause");
return 0;
}