Submission #2540998


Source Code Expand

Copy
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<utility>
#include<functional>
#include<iomanip>
#include<sstream>
#include<ctime>
#include<cassert>
using namespace std;
#define y0 y0z
#define y1 y1z
#define yn ynz
#define j0 j0z
#define j1 j1z
#define jn jnz
#define tm tmz
#define buli(x) (__builtin_popcountll(x))
#define bur0(x) (__builtin_ctzll(x))
#define bul2(x) (63-__builtin_clzll(x))
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fil(a,b) memset((a),(b),sizeof(a))
#define cl(a) fil(a,0)
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,a) for(__typeof((a).begin()) it=(a).begin();it!=(a).end();it++)
#define rep(i,a,b) for (int i=(a),_ed=(b);i<_ed;i++)
#define per(i,a,b) for (int i=(b)-1,_ed=(a);i>=_ed;i--)
#define forg(i,gu) for (int i=gu;~i;i=e[i].next)
#define pw(x) ((ll(1))<<(x))
#define upmo(a,b) (((a)=((a)+(b))%mo)<0?(a)+=mo:(a))
#define mmo(a,b) (((a)=1ll*(a)*(b)%mo)<0?(a)+=mo:(a))
void getre(){int x=0;printf("%d\n",1/x);}
void gettle(){int res=1;while(1)res<<=1;printf("%d\n",res);}
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
template<typename T,typename S>inline bool upmin(T&a,const S&b){return a>b?a=b,1:0;}
template<typename T,typename S>inline bool upmax(T&a,const S&b){return a<b?a=b,1:0;}
template<typename N,typename PN>inline N flo(N a,PN b){return a>=0?a/b:-((-a-1)/b)-1;}
template<typename N,typename PN>inline N cei(N a,PN b){return a>0?(a-1)/b+1:-(-a/b);}
template<typename N>N gcd(N a,N b){return b?gcd(b,a%b):a;}
template<typename N>inline int sgn(N a){return a>0?1:(a<0?-1:0);}
#if ( ( _WIN32 || __WIN32__ ) && __cplusplus < 201103L)
#define lld "%I64d"
#else
#define lld "%lld"
#endif
inline void gn(long long&x){
	int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');
	c=='-'?(sg=-1,x=0):(x=c-'0');
	while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg;
}
inline void gn(int&x){long long t;gn(t);x=t;}
inline void gn(unsigned long long&x){long long t;gn(t);x=t;}
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
inline void gn(long double&x){double t;scanf("%lf",&t);x=t;}
inline void gs(char *s){scanf("%s",s);}
inline void gc(char &c){while((c=getchar())>126 || c<33);}
inline void pc(char c){putchar(c);}
#ifdef JCVB
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
typedef long long ll;
typedef double db;
inline ll sqr(ll a){return a*a;}
inline db sqrf(db a){return a*a;}
const int inf=0x3f3f3f3f;
//const ll inf=0x3f3f3f3f3f3f3f3fll;
const db pi=3.14159265358979323846264338327950288L;
const db eps=1e-6;
//const int mo=0;
//int qp(int a,ll b){int n=1;do{if(b&1)n=1ll*n*a%mo;a=1ll*a*a%mo;}while(b>>=1);return n;}

int n;
vi chd[11111];

int qu[11111];
int d[11111];
int dis[11111];
int bfs(int u){
	int p=0,q=0;
	rep(i,1,n+1)dis[i]=-1;
	qu[q++]=u;
	dis[u]=0;
	while(p!=q){
		int u=qu[p++];
		for (auto v:chd[u]) {
			if(dis[v]!=-1)continue;
			dis[v]=dis[u]+1;
			qu[q++]=v;
		}
	}
}

vi leaf;

int needdeg[555];
int bfs2(){
	int p=0,q=0;
	rep(i,1,n+1)dis[i]=-1;
	rep(u,1,n+1)if(chd[u].size()==1) {
		dis[u]=0;
		qu[q++]=u;
	}
	while(p!=q){
		int u=qu[p++];
		for (auto v:chd[u]) {
			if(dis[v]!=-1)continue;
			dis[v]=dis[u]+1;
			qu[q++]=v;
		}
	}
}

ll gao() {
	cl(needdeg);
	leaf.clear();
	bfs(1);
	int u=1;
	rep(i,1,n+1)if(dis[i]>dis[u])u=i;
	bfs(u);
	int d=0;
	rep(i,1,n+1)upmax(d,dis[i]);
	rep(i,1,n+1)if(chd[i].size()==1) {
		leaf.pb(i);
	}
	int idtot=n;
	for (auto le:leaf) {
		bfs(le);
		int ma=0;
		rep(i,1,n+1)upmax(ma,dis[i]);
		int del = d - ma;
		int las=le;
		rep(j,0,del) {
			int ne = ++idtot;
			chd[las].pb(ne);
			chd[ne].pb(las);
			las=ne;
		}
	}
	n=idtot;
	bfs2();
	rep(u,1,n+1) {
		upmax(needdeg[dis[u]],chd[u].size());
	}
	ll ans=1;
	if(d%2==1) {
		rep(i,1,d/2+1)
			ans *= needdeg[i]-1;

		ans*=2;
	}else{
		rep(i,1,d/2)
			ans*=needdeg[i]-1;
		ans*=needdeg[d/2];
	}
	return ans;
}
int oldn;

vi  oldchd[111];
void clea() {
	rep(i,1,n+1)chd[i].clear();
	rep(i,1,oldn+1)chd[i]=oldchd[i];
	n=oldn;
}
int main()
{
	gn(n);
	oldn=n;
	rep(i,1,n){
		int u,v;
		gn(u);gn(v);
		chd[u].pb(v);
		chd[v].pb(u);
	}
	rep(i,1,n+1)oldchd[i]=chd[i];
	bfs(1);
	int u=1;
	rep(i,1,n+1)if(dis[i]>dis[u])u=i;
	bfs(u);
	int d=0;
	rep(i,1,n+1)upmax(d,dis[i]);
	rep(i,1,n+1)if(chd[i].size()==1) {
		leaf.pb(i);
	}
	int idtot=n;
	for (auto le:leaf) {
		bfs(le);
		int ma=0;
		rep(i,1,n+1)upmax(ma,dis[i]);
		int del = d - ma;
		int las=le;
		rep(j,0,del) {
			int ne = ++idtot;
			chd[las].pb(ne);
			chd[ne].pb(las);
			las=ne;
		}
	}
	n=idtot;
	bfs2();
	rep(u,1,n+1) {
		upmax(needdeg[dis[u]],chd[u].size());
	}
	ll ans=1;
	if(d%2==1) {
		rep(i,1,d/2+1)
			ans *= needdeg[i]-1;

		ans*=2;
	}else{
		rep(i,1,d/2)
			ans*=needdeg[i]-1;
		ans*=needdeg[d/2];
		rep(u,1,oldn+1){
			clea();
			chd[u].pb(n+1);
			chd[n+1].pb(u);
			n++;
			upmin(ans,gao());
		}
	}
	cout<<d/2+1<<" ";
	cout<<ans<<endl;
	return 0;

}

Submission Info

Submission Time
Task D - Isomorphism Freak
User jcvb
Language C++14 (GCC 5.4.1)
Score 0
Code Size 5308 Byte
Status
Exec Time 10 ms
Memory 512 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt
All 0 / 1100 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, 55.txt, 56.txt, 57.txt, 58.txt, 59.txt, 60.txt, 61.txt, 62.txt, 63.txt, 64.txt, 65.txt, 66.txt, 67.txt, 68.txt, 69.txt, 70.txt, 71.txt, 72.txt, 73.txt, 74.txt, 75.txt, 76.txt, 77.txt, 78.txt, 79.txt, 80.txt, 81.txt, 82.txt, 83.txt, 84.txt, 85.txt, 86.txt, 87.txt, 88.txt, 89.txt, 90.txt, 91.txt, 92.txt, 93.txt, 94.txt, 95.txt, 96.txt, 97.txt, 98.txt, 99.txt, s1.txt, s2.txt, s3.txt, s4.txt
Case Name Status Exec Time Memory
01.txt 1 ms 512 KB
02.txt 7 ms 512 KB
03.txt 6 ms 512 KB
04.txt 8 ms 512 KB
05.txt 6 ms 512 KB
06.txt 5 ms 512 KB
07.txt 2 ms 512 KB
08.txt 1 ms 512 KB
09.txt 5 ms 512 KB
10.txt 5 ms 512 KB
11.txt 1 ms 512 KB
12.txt 2 ms 512 KB
13.txt 2 ms 512 KB
14.txt 1 ms 512 KB
15.txt 2 ms 512 KB
16.txt 2 ms 512 KB
17.txt 2 ms 512 KB
18.txt 2 ms 512 KB
19.txt 1 ms 512 KB
20.txt 1 ms 512 KB
21.txt 1 ms 512 KB
22.txt 1 ms 512 KB
23.txt 1 ms 512 KB
24.txt 2 ms 512 KB
25.txt 1 ms 512 KB
26.txt 2 ms 512 KB
27.txt 7 ms 512 KB
28.txt 6 ms 512 KB
29.txt 4 ms 512 KB
30.txt 8 ms 512 KB
31.txt 8 ms 512 KB
32.txt 8 ms 512 KB
33.txt 7 ms 512 KB
34.txt 8 ms 512 KB
35.txt 7 ms 512 KB
36.txt 8 ms 512 KB
37.txt 7 ms 512 KB
38.txt 6 ms 512 KB
39.txt 2 ms 512 KB
40.txt 1 ms 512 KB
41.txt 2 ms 512 KB
42.txt 2 ms 512 KB
43.txt 2 ms 512 KB
44.txt 1 ms 512 KB
45.txt 2 ms 512 KB
46.txt 2 ms 512 KB
47.txt 8 ms 512 KB
48.txt 9 ms 512 KB
49.txt 7 ms 512 KB
50.txt 7 ms 512 KB
51.txt 7 ms 512 KB
52.txt 8 ms 512 KB
53.txt 9 ms 512 KB
54.txt 3 ms 512 KB
55.txt 3 ms 512 KB
56.txt 6 ms 512 KB
57.txt 2 ms 512 KB
58.txt 2 ms 512 KB
59.txt 4 ms 512 KB
60.txt 5 ms 512 KB
61.txt 5 ms 512 KB
62.txt 5 ms 512 KB
63.txt 3 ms 512 KB
64.txt 4 ms 512 KB
65.txt 6 ms 512 KB
66.txt 3 ms 512 KB
67.txt 2 ms 512 KB
68.txt 6 ms 512 KB
69.txt 2 ms 512 KB
70.txt 5 ms 512 KB
71.txt 4 ms 512 KB
72.txt 7 ms 512 KB
73.txt 3 ms 512 KB
74.txt 3 ms 512 KB
75.txt 3 ms 512 KB
76.txt 6 ms 512 KB
77.txt 8 ms 512 KB
78.txt 6 ms 512 KB
79.txt 6 ms 512 KB
80.txt 6 ms 512 KB
81.txt 5 ms 512 KB
82.txt 10 ms 512 KB
83.txt 5 ms 512 KB
84.txt 7 ms 512 KB
85.txt 4 ms 512 KB
86.txt 4 ms 512 KB
87.txt 5 ms 512 KB
88.txt 2 ms 512 KB
89.txt 9 ms 512 KB
90.txt 8 ms 512 KB
91.txt 6 ms 512 KB
92.txt 10 ms 512 KB
93.txt 1 ms 512 KB
94.txt 1 ms 512 KB
95.txt 1 ms 512 KB
96.txt 1 ms 512 KB
97.txt 1 ms 512 KB
98.txt 1 ms 512 KB
99.txt 1 ms 512 KB
s1.txt 1 ms 512 KB
s2.txt 1 ms 512 KB
s3.txt 1 ms 512 KB
s4.txt 1 ms 512 KB