比赛 |
NOIP模拟赛by mzx Day2 |
评测结果 |
AAAAAAAAAA |
题目名称 |
森林大礼包 |
最终得分 |
100 |
用户昵称 |
ミント |
运行时间 |
2.266 s |
代码语言 |
C++ |
内存使用 |
65.29 MiB |
提交时间 |
2016-10-20 21:15:30 |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <malloc.h>
using namespace std;
/*const int maxn = 100000 + 100;
const int mod = 1000000000 + 7;
int rank[maxn], ufs[maxn];
long long nuts[maxn];
inline int find(int x){
if(x==ufs[x])return ufs[x];
return ufs[x] = find(ufs[x]);
}
inline void merge(int x, int y){
int tx = find(x), ty = find(y);
if(rank[tx]>rank[ty]){
ufs[ty] = tx;
nuts[ty] = (nuts[ty] + nuts[tx]) % mod;
}
else {
ufs[tx] = ty;
nuts[tx] = (nuts[ty] + nuts[tx]) % mod;
if(rank[tx]==rank[ty])rank[ty]++;
}return ;
}
int main(){
freopen("three_squirrels.in", "r", stdin);
freopen("three_squirrels.out", "w", stdout);
memset(rank, 0, sizeof(rank));
memset(nuts, 0, sizeof(nuts));
for(int i=0;i<maxn;i++)ufs[i] = i;
nuts[0] = 1;
int n;cin>>n;
for(int i=1;i<=n;i++){
int k;cin>>k;
while(k--){
int tmp;cin>>tmp;
merge(i, tmp);
}
for(int i=1;i<=n;i++)cout<<nuts[find(i)]<<' ';cout<<endl;
for(int i=1;i<=n;i++)cout<<ufs[i]<<' ';cout<<endl;
}cout<<nuts[find(n)]%mod<<endl;
return 0;
}//*/
const int maxn = 100000 + 100;
const int mod = 1000000000 + 7;
long long nuts[maxn];
bool vis[maxn];
vector<int> G[maxn];
/*inline void DFS(int u){
vis[u] = true;
for(int i=0;i<G[u].size();i++){
int v = G[u][i];
if(!vis[v])DFS(v);
nuts[u] += nuts[v];nuts[u] %= mod;
}return ;
}//*/
inline long long DFS(int u){
if(vis[u])return nuts[u] % mod;
vis[u] = true;
for(int i=0;i<G[u].size();i++){
nuts[u] += DFS(G[u][i]) % mod;
nuts[u] %= mod;
}return nuts[u];
}
int main(){
int __size__=128<<20;
char *__p__=(char*)malloc(__size__)+__size__;
__asm__("movl %0, %%esp\n"::"r"(__p__));
freopen("three_squirrels.in", "r", stdin);
//freopen("out.txt", "r", stdin);
freopen("three_squirrels.out", "w", stdout);
memset(nuts, 0, sizeof(nuts));nuts[0] = 1;
memset(vis, false, sizeof(vis));vis[0] = true;
int n;cin>>n;
for(int i=1;i<=n;i++){
int k;cin>>k;
while(k--){
int tmp;cin>>tmp;
G[i].push_back(tmp);
}
}
cout<<DFS(n)%mod<<endl;//cout<<nuts[n]%mod<<endl;
//for(int i=1;i<=n;i++)cout<<nuts[i]<<' ';cout<<endl;
return 0;
}