WA on #14 #15

直接复制的LCA板子。qwq

谁来帮助一下我会关注哦。qwq

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c,x,y,fa[210],tot=1,en=1,lg[500010];
//lg是求log，fa是并查集，en是邻接表的一个小变量
string s1,s2;
map<string,int> m;//类似离散化吧
int findfa(int x)//并查集
{
	if(fa[x]==x)
		return x;
	return fa[x]=findfa(fa[x]);
}
struct POINT//邻接表
{
	int head,deep,fa[40];
	string name;
}p[500010];
struct EDGE//邻接表
{
	int nxt,num;
}e[1000010];
int addline(int x,int y)//邻接表加边
{
	e[en].num=y;
	e[en].nxt=p[x].head;
	p[x].head=en;
	en++;
	return 0;
}
int dfs(int deep,int fa,int now)//就是LCA的dfs
{
	p[now].fa[0]=fa;
	p[now].deep=deep;
	for(int i=1;i<=lg[n]+1;i++)
		if(p[p[now].fa[i-1]].fa[i-1]>0)
			p[now].fa[i]=p[p[now].fa[i-1]].fa[i-1];
	for(int i=p[now].head;i>0;i=e[i].nxt)
		if(e[i].num!=fa)
			dfs(deep+1,now,e[i].num);
	return 0;
}
int LCA(int x,int y)//LCA板子
{
	if(p[x].deep<p[y].deep)
		swap(x,y);
	while(p[x].deep>p[y].deep)
		x=p[x].fa[lg[p[x].deep-p[y].deep]-1];
	if(x==y)
		return x;
	for(int i=lg[n];i>=0;i--)
	{
		if(p[x].fa[i]!=p[y].fa[i])
		{
			x=p[x].fa[i];
			y=p[y].fa[i];
		}
	}
	return p[x].fa[0];
}
int main()
{
	scanf("%d",&n);
	cin>>s1;
	m[s1]=tot;
	p[tot].name=s1;
	tot++;
	cin>>s2;
	m[s2]=tot;
	p[tot].name=s2;
	tot++;//输入要求的两只牛
	a=m[s1],b=m[s2];//用a、b记下来
	fa[1]=1,fa[2]=2;//并查集初始化
	for(int i=1;i<=n;i++)
	{
		cin>>s1>>s2;
		if(m.find(s1)==m.end())//这只牛没出现过
		{
			m[s1]=tot;
			p[tot].name=s1;//类似离散化
			fa[tot]=tot;//并查集初始化
			tot++;
		}
		if(m.find(s2)==m.end())//同上一个if
		{
			m[s2]=tot;
			p[tot].name=s2;
			fa[tot]=tot;
			tot++;
		}
		x=m[s1],y=m[s2];
		fa[y]=x;//并查集
		addline(x,y);//加边
		addline(y,x);
	}
	if(findfa(a)!=findfa(b))//并查集判断无关
	{
		printf("NOT RELATED");
		return 0;
	}
	dfs(1,0,findfa(a));
	for(int i=1;i<=100010;i++)
		lg[i]=lg[i/2]+1;
	c=LCA(a,b);//LCA板子
	if(p[a].fa[0]==p[b].fa[0])//判姐妹
	{
		printf("SIBLINGS");
		return 0;
	}
	if(b==c)//判直系母亲
		swap(a,b);
	if(a==c)
	{
		cout<<p[a].name;
		printf(" is the ");
		if(p[b].deep-p[a].deep==1)
			printf("mother");
		else
		{
			for(int i=1;i<=p[b].deep-p[a].deep-2;i++)
				printf("great-");
			printf("grand-mother");
		}
		printf(" of ");
		cout<<p[b].name;
		return 0;
	}
	if(p[b].fa[0]==c)//判aunt系
		swap(a,b);
	if(p[a].fa[0]==c)
	{
		cout<<p[a].name;
		printf(" is the ");
		for(int i=1;i<=p[b].deep-p[a].deep-1;i++)
			printf("great-");
		printf("aunt of ");
		cout<<p[b].name;
		return 0;
	}
	printf("COUSINS");//其他都不是，cousin
	return 0;
}