結果

問題 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