fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // #define DEBUG
  5.  
  6. using ll = long long;
  7. using ii = pair<int, int>;
  8. using vi = vector<int>;
  9. using vii = vector<ii>;
  10. using vll = vector<ll>;
  11. using si = set<int>;
  12. using sll = set<ll>;
  13.  
  14. vector<vi> adj;
  15. vector<bool> visited;
  16. vi topsort;
  17. const int mod = 1e9 + 7;
  18.  
  19. void ts(int v){
  20.     visited[v] = true;
  21.     for (int i = 0; i < adj[v].size(); i++){
  22.         int u = adj[v][i];
  23.         if (!visited[u]) ts(u);
  24.     }
  25.     topsort.push_back(v);
  26. }
  27.  
  28. int main(){
  29. 	#ifdef DEBUG
  30. 	freopen("out.txt", "w", stdout);
  31. 	#endif
  32. 	cin.tie(NULL);
  33. 	ios_base::sync_with_stdio(false);
  34.  
  35.     int n, l;
  36.     cin >> n >> l;
  37.     adj.resize(n + 1);
  38.     for (int i = 1; i <= l; i++){
  39.         int k; cin >> k;
  40.         for (int j = 0; j < k; j++){
  41.             int x; cin >> x;
  42.             adj[i].push_back(x);
  43.         }
  44.     }
  45.     visited.assign(n + 1, false);
  46.     ts(1);
  47.     reverse(topsort.begin(), topsort.end());
  48.     vll dp(n + 1);
  49.     dp[1] = 1;
  50.     for (int i = 0; i < topsort.size(); i++){
  51.         int v = topsort[i];
  52.         for (int j = 0; j < adj[v].size(); j++){
  53.             int u = adj[v][j];
  54.             dp[u] = (dp[u] + dp[v]) % mod;
  55.         }
  56.     }
  57.     ll total = 0;
  58.     ll once = 0;
  59.     for (int i = l + 1; i <= n; i++){
  60.         if (dp[i] > 0) once++;
  61.         total = (total + dp[i]) % mod;
  62.     }
  63.     cout << total << " " << once << endl;
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
10 5
4 8 9 10 3
3 9 10 6
3 8 9 7
6 2 3 6 7 8 10
5 9 10 3 1 7
stdout
copy 
6 4
https://ideone.com/61vnoj
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!