結果

問題 No.758 VVVVV
ユーザー akakimidoriakakimidori
提出日時 2018-12-06 08:51:09
言語 C
(gcc 12.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
13,756 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 4 ms
6,944 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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;
}
0