比赛 |
不平凡的世界 |
评测结果 |
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;
}