TLE+MLE大礼包,求助!!!
查看原帖
TLE+MLE大礼包,求助!!!
475143
gaojian2007楼主2021/10/13 09:43
#include<iostream> 
#include<vector>
#include<cstdio>
using namespace std;
int n,m,maxx,lca[5000006],now;
vector<int>shen[500006];
inline int read() {
		int __x=0,__f=1;
		char __c=getchar();
		while(__c<'0'||__c>'9') {
			if(__c=='-')__f=-1;
			__c=getchar();
		}
		while(__c>='0'&&__c<='9') {
			__x=__x*10+__c-'0';
			__c=getchar();
		}
		return __x*__f;
	}
	char __F[200];
	inline void write(int __x) {
		if(__x==0) {
			putchar('0');
			return;
		}
		int __tmp,__cnt=0;
		if(__x>0) {
			__tmp=__x;
		} else {
			__tmp=-__x;
		}
		if(__x<0) {
			putchar('-');
		}
		while(__tmp>0) {
			__F[__cnt++]=__tmp%10+'0';
			__tmp/=10;
		}
		while(__cnt>0) {
			putchar(__F[--__cnt]);
		}
	}
struct node
{
	int fa;
	vector<int>hai;
	int f;
}a[5000006];
int dfs(int d,int x)
{
	shen[x].push_back(d);
	if(x>maxx)
	maxx=x;
	if(a[d].hai.size()!=0)
	{
		int maxn=0;
		for(int i=0;i<a[d].hai.size();i++)
	{
		maxn=max(maxn,dfs(a[d].hai[i],x+1));
	}
	a[d].f=maxn;
	return maxn;
}
	else
	return a[d].f=x;
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		int x;
		x=read();
		if(x==0)
		{
			a[1].fa=0;
		}
		a[i].fa=x;
		a[x].hai.push_back(i);
	}
	dfs(1,1);
	now=maxx;
	for(int i=maxx;i>=1;i--)
	{
		if(shen[i].size()==1)
		{
			for(int j=i;j<=now;j++)
			if(lca[j]==0)
			{
				lca[j]=shen[i][0];
			}
			now=i-1;
			continue;
		}
		int q1=0,q2=0,qj=0;
		for(int j=0;j<shen[i].size();j++)
		{
			if(a[shen[i][j]].f>q1)
			{
				q2=q1;
				q1=a[shen[i][j]].f;
				qj=shen[i][j];
				continue;
			}
			if(a[shen[i][j]].f>q2)
			{
				q2=a[shen[i][j]].f;
			}
		}
		for(int j=q2+1;j<=now;j++)
		if(lca[j]==0)
		{
			lca[j]=qj;
		}
		now=q2;
	}
	for(int i=1;i<=m;i++)
	{
		int x;
		x=read();
		write(lca[x]);
		puts("");
	}
	return 0;
}
2021/10/13 09:43
加载中...