Advertisement
savrasov

RANDOMNAME

Jun 20th, 2017
364
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.71 KB | None | 0 0
  1. //#include "stdafx.h"
  2. #include <algorithm>
  3. #include <iostream>
  4. #include <string>
  5. #include <cstring>
  6. #include <fstream>
  7. #include <cmath>
  8. #include <vector>
  9. #include <utility>
  10. #include <cstdlib>
  11. #include <deque>
  12. #include <queue>
  13. #include <iomanip>
  14. #include <numeric>
  15. #include <stack>
  16. #include <map>
  17. #include <set>
  18. #include <cmath>
  19. #include <list>
  20. #define mp make_pair
  21. #define pb push_back
  22. #define xx first
  23. #define yy second
  24. #define preturn(a) return cout << a << endl, 0
  25.  
  26. using namespace std;
  27.  
  28. typedef long long ll;
  29. typedef unsigned long long ull;
  30. typedef long double ld;
  31. typedef unsigned int uint;
  32. const int N = (int)2500000, md = 1e7;
  33. const ld eps = 1e-16, eps1 = 1e-10, OOO = 1e200, PI = 3.14159265358979323846;
  34. const ull OOU = 1e19 * 1.7;
  35. const ll OO = 1e18 * 8, mod = 1e9 + 7;
  36.  
  37. int d[300000], q[(int)(1e7 * 1.1)], h, t, pr[300000];
  38. vector<vector<pair<int, pair<bool, bool> > > > g(200001);// , g1(200001);
  39. vector<bool> debt(N), used(N);
  40. set<pair<int, int> > us;
  41.  
  42. int add(int a, int b)
  43. {
  44.     if (a == -1 || b == -1) return -1;
  45.     else return ((a + b) % mod);
  46. }
  47.  
  48. int main()
  49. {
  50.     //ios_base::sync_with_stdio(0);
  51.     //freopen("easy1.txt", "r", stdin);
  52.     //freopen("output.txt", "w", stdout);
  53.     d[0] = 1;
  54.     int n, m, a, b, v;
  55.     cin >> n >> m;
  56.     for (int i = 0; i < m; i++)
  57.     {
  58.         scanf("%d%d", &a, &b);
  59.         a--;
  60.         b--;
  61.         g[a].pb(mp(b, mp(0, 0)));
  62.         pr[b]++;
  63.         //if (g[b].find(a) != g[b].end()) d[a] = d[b] = pr[a] = pr[b] = -1;
  64.     }
  65.     //cout << clock() << endl;
  66.     q[h++] = 0;
  67.     used[0] = 1;
  68.     for (; h != t;)
  69.     {
  70.         v = q[t++];
  71.         t %= md;
  72.         for (vector<pair<int, pair<bool, bool> > >::iterator i = g[v].begin(); i != g[v].end(); i++)
  73.         {
  74.             if (i->yy.xx)
  75.             {
  76.                 d[i->xx] = d[v] = pr[i->xx] = pr[v] = -1;
  77.                 debt[v] = 1;
  78.                 continue;
  79.             }
  80.             else i->yy.xx = 1;
  81.             if (pr[v] <= 0)
  82.             {
  83.                 d[i->xx] = add(d[i->xx], d[v]);
  84.                 pr[i->xx]--;
  85.                 //debt[v] = 1;
  86.                 if (!used[i->xx])
  87.                 {
  88.                     q[h++] = i->xx;
  89.                     h %= md;
  90.                     used[i->xx] = 1;
  91.                     debt[v] = 0;
  92.                 }
  93.             }
  94.             else
  95.             {
  96.                 debt[v] = 1;
  97.                 q[h++] = i->xx;
  98.                 h %= md;
  99.             }
  100.         }
  101.     }
  102.     h = t = 0;
  103.     q[h++] = 0;
  104.     //cout << clock() << endl;
  105.     //fill(used.begin(), used.end(), 0);
  106.     used[0] = 1;
  107.     for (; h != t;)
  108.     {
  109.         v = q[t++];
  110.         t %= md;
  111.         if (pr[v] > 0)
  112.         {
  113.             q[h++] = v;
  114.             h %= md;
  115.             continue;
  116.         }
  117.         for (vector<pair<int, pair<bool, bool> > >::iterator i = g[v].begin(); i != g[v].end(); i++)
  118.         {
  119.             if (debt[v]) d[i->xx] = add(d[i->xx], d[v]), pr[i -> xx]--;
  120.             if (!(i->yy.yy))
  121.             {
  122.                 q[h++] = i->xx;
  123.                 h %= md;
  124.                 i->yy.yy = 1;
  125.                 pr[i->xx]--;
  126.             }
  127.         }
  128.         debt[v] = 0;
  129.     }
  130.     //cout << clock() << endl;
  131.     for (int i = 1; i < n; i++) printf("%d\n", d[i]);
  132.     //cout << endl << clock();
  133.     return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement