結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2019-02-08 07:11:28 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 68 ms / 2,000 ms |
コード長 | 1,612 bytes |
コンパイル時間 | 914 ms |
コンパイル使用メモリ | 30,208 KB |
実行使用メモリ | 22,912 KB |
最終ジャッジ日時 | 2024-10-14 01:58:30 |
合計ジャッジ時間 | 2,086 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include<stdio.h>#include<stdlib.h>typedef struct directedGraph{int *vertex;int *next;int *start;int v,e;int pointer;} graph;graph* newGraph(const int v,const int e){graph *g=(graph *)malloc(sizeof(graph));g->vertex=(int *)calloc(e,sizeof(int));g->next=(int *)calloc(e,sizeof(int));g->start=(int *)calloc(v,sizeof(int));for(int i=0;i<v;i++) g->start[i]=-1;g->v=v;g->e=e;g->pointer=0;return g;}void freeGraph(graph *g){free(g->vertex);free(g->next);free(g->start);free(g);return;}void addEdge(graph *g,const int from,const int to){const int p=g->pointer;g->vertex[p]=to;g->next[p]=g->start[from];g->start[from]=p;g->pointer++;return;}typedef long long int int64;void add(int *bit,int index,int v){index++;const int n=bit[0];for(int i=index;i<=n;i+=i&-i) bit[i]+=v;}int sum(int *bit,int index){index++;int res=0;for(int i=index;i>0;i-=i&-i) res+=bit[i];return res;}int64 calc(int v,int *bit,graph *g,int *used){if(used[v]) return 0;used[v]=1;int64 res=sum(bit,v);add(bit,v,1);for(int p=g->start[v];p!=-1;p=g->next[p]){int u=g->vertex[p];res+=calc(u,bit,g,used);}add(bit,v,-1);return res;}void run(void){int n;scanf("%d",&n);graph *g=newGraph(n,2*n);int i;for(i=1;i<n;i++){int a;scanf("%d",&a);addEdge(g,a,i);addEdge(g,i,a);}int *bit=(int *)calloc(n+1,sizeof(int));bit[0]=n;int *used=(int *)calloc(n,sizeof(int));int64 ans=calc(0,bit,g,used);printf("%lld\n",ans);}int main(void){run();return 0;}