比赛 不平凡的世界 评测结果 AWWWWWWWWW
题目名称 不平凡的许愿树 最终得分 10
用户昵称 WAHT 运行时间 13.205 s
代码语言 C++ 内存使用 12.20 MiB
提交时间 2015-11-05 11:59:06
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int read()
{
	int x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0') ch=getchar();
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0',ch=getchar();}
	return x;
}
const int oo=300000;
struct my
{
	int next,y,v;
}e[oo];
int linkk[oo],len,ru[oo];
void insert(int xx,int yy)
{
	e[++len].y=yy;
	e[len].next=linkk[xx];
	linkk[xx]=len;
	e[++len].y=xx;
	e[len].next=linkk[yy];
	linkk[yy]=len;
}
int q[oo],head,tail,deep[oo],num[oo];
int ans;
bool vis[oo];
int m;
void bfs(int s)
{
	deep[s]=0;
	q[1]=s,tail=1,head=0;
	memset(num,0,sizeof(num));
	memset(vis,0,sizeof(vis));
	vis[s]=1;
	while(head++<tail)
	{
		int tn=q[head];
		for(int i=linkk[tn];i;i=e[i].next)
		{	
			int to=e[i].y;
			if(!vis[to])
			{	
				vis[to]=1;
				q[++tail]=to;
				deep[to]=deep[tn]+1;
				num[deep[to]]++;
			}
		}
	}
	for(int i=1;i<=m;i++)
	{
		if(num[i]==0) return;
		int num1=0;
		if(num[i]>=2) num1=1;
		for(int j=4;j<=num[i];j++)
		{	num1=num1*j,num1%=388;}
		ans=(ans+num1)%388;
	}
}
int map[800][800];
void init()
{
	m=read();
	int a,b;
	if(m>800)
	{
		for(int i=1;i<m;i++)
		{a=read(),b=read();ru[a]++,ru[b]++;	insert(a,b);}
	

		for(int i=1;i<=m+1;i++)
		{	bfs(i);}
	}
	else	
	{
		memset(map,10,sizeof(map));
			for(int i=1;i<m;i++)
		{a=read(),b=read();map[a][b]=map[b][a]=1;}
		int n=m+1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++ )
				for(int k=1;k<=n;k++)
					map[j][k]=min(map[j][k],map[j][i]+map[i][k]);
				
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=n;k++)
					if(i==j==k) continue;
					else
						if(map[i][j]==map[i][k]==map[k][j]&&map[i][j]!=map[0][0]) ans++,ans%=388;
	}
	cout<<ans+1<<' '<<(ans+233)%388+1;
}

int main()
{
	freopen("hopetree.in","r",stdin);
	freopen("hopetree.out","w",stdout);
	
	init();
	return 0;
}