結果

問題 No.758 VVVVV
ユーザー akakimidori
提出日時 2018-12-06 08:51:09
言語 C
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 4,286 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 36,100 KB
実行使用メモリ 21,408 KB
最終ジャッジ日時 2024-09-13 23:03:51
合計ジャッジ時間 4,001 ms
ジャッジサーバーID
(参考情報)
judge4 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 3
other AC * 3 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<assert.h>
typedef struct AVLTreeNode{
int size;
int rank;
int bias;
struct AVLTreeNode *left;
struct AVLTreeNode *right;
unsigned char val[];
} AVLNode;
typedef struct AVLTreeHead{
AVLNode *root;
size_t valSize;
int (*cmp)(const void *,const void *);
} AVLTree;
int getRank(const AVLNode *t){
return t==NULL?0:t->rank;
}
int getSize(const AVLNode *t){
return t==NULL?0:t->size;
}
int getBias(const AVLNode *t){
return t==NULL?0:t->bias;
}
AVLNode* newAVLNode(const void *v,const size_t size){
AVLNode *res=(AVLNode *)malloc(sizeof(AVLNode)+size);
memcpy(res->val,v,size);
res->size=1;
res->rank=1;
res->bias=0;
res->left=NULL;
res->right=NULL;
return res;
}
void freeAllAVLNode(AVLNode *t){
if(t==NULL) return;
freeAllAVLNode(t->left);
freeAllAVLNode(t->right);
free(t);
}
void freeAVLNode(AVLNode *t){
free(t);
return;
}
AVLTree* newAVLTree(const size_t size,int (*cmp)(const void *,const void *)){
AVLTree *res=(AVLTree *)malloc(sizeof(AVLTree));
res->root=NULL;
res->valSize=size;
res->cmp=cmp;
return res;
}
void update(AVLNode *t){
if(t==NULL) return;
int lrank=getRank(t->left);
int rrank=getRank(t->right);
t->rank=1+(lrank>rrank?lrank:rrank);
t->size=1+getSize(t->left)+getSize(t->right);
t->bias=lrank-rrank;
return;
}
AVLNode* leftRotate(AVLNode *v){
AVLNode *u=v->right;
v->right=u->left;
u->left=v;
update(v);
update(u);
return u;
}
AVLNode* rightRotate(AVLNode *u){
AVLNode *v=u->left;
u->left=v->right;
v->right=u;
update(u);
update(v);
return v;
}
AVLNode* balance(AVLNode *t){
if(t==NULL) return NULL;
int b=getBias(t);
if(b<=-2){
if(getBias(t->right)>0) t->right=rightRotate(t->right);
t=leftRotate(t);
} else if(b>=2){
if(getBias(t->left)<0) t->left=leftRotate(t->left);
t=rightRotate(t);
}
return t;
}
AVLNode* insert_func(AVLNode *r,const void *v,AVLTree *t){
if(r==NULL) return newAVLNode(v,t->valSize);
if(t->cmp(r->val,v)>=0){
r->left=insert_func(r->left,v,t);
} else {
r->right=insert_func(r->right,v,t);
}
update(r);
return balance(r);
}
void insert(AVLTree *t,const void *v){
t->root=insert_func(t->root,v,t);
return;
}
int search(AVLTree *t,void *res){
AVLNode *r=t->root;
while(r!=NULL){
int c=t->cmp(r->val,res);
if(c==0){
memcpy(res,r->val,t->valSize);
return 1;
} else if(c>0){
r=r->left;
} else {
r=r->right;
}
}
return 0;
}
typedef long long int int64;
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))
const int mod=1000000000+7;
int *fact=NULL;
int *iFact=NULL;
void init(const int n){
fact=(int *)calloc(n+1,sizeof(int));
fact[0]=1;
int i;
for(i=1;i<=n;i++) fact[i]=(int64)fact[i-1]*i%mod;
int t=1;
int a=fact[n];
while(a>1){
t=(int64)t*(mod-mod/a)%mod;
a=mod%a;
}
iFact=(int *)calloc(n+1,sizeof(int));
iFact[n]=t;
for(i=n-1;i>=0;i--) iFact[i]=(int64)iFact[i+1]*(i+1)%mod;
}
int comb(int n,int k){
if(!(0<=k && k<=n)) return 0;
return (int64)fact[n]*iFact[k]%mod*iFact[n-k]%mod;
}
typedef struct {
int n;
int leaf;
int val;
} node;
int cmp(const void *a,const void *b){
const node *p=(const node *)a;
const node *q=(const node *)b;
if(p->n !=q->n) return p->n-q->n;
if(p->leaf!=q->leaf) return p->leaf-q->leaf;
return 0;
}
int f(const int n,const int l){
if(l==1) return 1;
if(l>n) return 0;
static AVLTree *map=NULL;
if(map==NULL) map=newAVLTree(sizeof(node),cmp);
node t={n,l,0};
if(search(map,&t)) return t.val;
int res=f(n-1,l);
int i,j;
for(i=1;i<n-1;i++){
for(j=1;j<l;j++){
res=(res+(int64)f(i,j)*f(n-i,l-j))%mod;
}
}
t.val=res;
insert(map,&t);
return res;
}
void run(void){
int n;
scanf("%d",&n);
if(n==1){
printf("1\n");
return;
}
int *cnt=(int *)calloc(n+1,sizeof(int));
int i;
for(i=0;i<n-1;i++){
int a,b;
scanf("%d%d",&a,&b);
cnt[a]++;
cnt[b]++;
}
int leaf=0;
for(i=2;i<=n;i++){
if(cnt[i]==1) leaf++;
}
init(200000);
int ans=f(n,leaf);
//int ans=calc(n,1,leaf);
printf("%d\n",ans);
}
int main(void){
run();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0