結果
問題 | No.758 VVVVV |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}