MLE*15!!!
  • 板块学术版
  • 楼主liaoyichen
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/12/12 12:04
  • 上次更新2023/11/3 22:23:52
查看原帖
MLE*15!!!
486675
liaoyichen楼主2021/12/12 12:04

此题绿题,但总是在第十个点MLE

my code:

//CF767C
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000010,M=N*2;
int n,sum=0;
int a[N];
int v[N];
int head[N],ver[M],nex[M],tot=0;
int daan[5],id=0;
inline int read()
{   register int f=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {   if(ch=='-')
        {   w=-1;   
        }
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {   f=f*10+ch-'0';
        ch=getchar();   
    }
    return f*w;
}
void add(int x,int y){
	ver[++tot]=y;
	nex[tot]=head[x];
	head[x]=tot;
}
void dfs(int x,int z){
	v[x]=a[x];
	for(int i=head[x];i;i=nex[i]){
		int y=ver[i];
		if(y==z){
			continue;
		}
		//f[y]=x;
		dfs(y,x);
		v[x]+=v[y];
	}
	if(v[x]==sum){
		//cout<<v[x]<<" "<<sum/3<<endl;
		daan[++id]=x;
		v[x]=0;
	}
	return;
}
signed main(){
	int m;
	n=read();
	for(int i=1;i<=n;i++){
		int x;
		x=read();a[i]=read();
		//v[i]=a[i];
		sum+=a[i];
		if(x==0){
			m=i;
		}
		else{
			add(x,i);
			add(i,x);
		}
	}
	if(sum%3){
		cout<<-1;
		return 0;
	}
	else{
		sum/=3;
		dfs(m,0);
		if(id>=3){
			/*if(daan[1]>daan[2]){
				swap(daan[1],daan[2]);
			}*/
			cout<<daan[1]<<" "<<daan[2];
		}
		else{
			cout<<-1;
		}
	}
} 
2021/12/12 12:04
加载中...