比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAWWWWWW
题目名称 森林大礼包 最终得分 40
用户昵称 SOBER GOOD BOY 运行时间 0.867 s
代码语言 C++ 内存使用 12.53 MiB
提交时间 2016-10-20 18:55:57
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100000+100;

int N,len;

int f[maxn],head[maxn];

struct edge
{
       int to,next;
}e[maxn*15];

void ADD(int x,int y)
{
     len++;
     e[len].to=y;
     e[len].next=head[x];
     head[x]=len;
}

int dp(int x)
{
    if(f[x]!=-1)return f[x];
    f[x]=0;
    for(int t,i=head[x];i;i=e[i].next)
    {
        t=e[i].to;
        f[x]+=dp(t);    
    }
    return f[x];
}

int main()
{
    freopen("three_squirrels.in","r",stdin);
    freopen("three_squirrels.out","w",stdout);
    scanf("%d",&N);
    memset(f,-1,sizeof(f));
    f[0]=1;
    for(int M,i=1;i<=N;i++)
    {
     scanf("%d",&M);
     for(int x,j=1;j<=M;j++)
     {
         scanf("%d",&x);
         ADD(i,x);    
     }       
    }
    printf("%d",dp(N));
    fclose(stdin);
    fclose(stdout);
    return 0;
}