Advertisement
savrasov

DEBUUUUUUUG

Jun 19th, 2017
387
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.03 KB | None | 0 0
  1. int d[300000], q[30000000], h, t, pr[300000];
  2. vector<vector<pair<int, pair<bool, bool> > > > g(200001);// , g1(200001);
  3. vector<bool> debt(N), used(N);
  4. set<pair<int, int> > us;
  5.  
  6. int add(int a, int b)
  7. {
  8.     if (a == -1 || b == -1) return -1;
  9.     else return ((a + b) % mod);
  10. }
  11.  
  12. int main()
  13. {
  14.     d[0] = 1;
  15.     int n, m, a, b, v;
  16.     cin >> n >> m;
  17.     for (int i = 0; i < m; i++)//начинается чтение графа
  18.     {
  19.         scanf("%d%d", &a, &b);
  20.         a--;
  21.         b--;
  22.         g[a].pb(mp(b, mp(0, 0)));
  23.         pr[b]++;//считаю предков этой вершины
  24.     }//конец чтения графа
  25.     q[h++] = 0;
  26.     used[0] = 1;
  27.     for (; h != t;)//пока очередь непуста
  28.     {
  29.         v = q[t++];
  30.         t %= md;//не обращай внимания
  31.         for (vector<pair<int, pair<bool, bool> > >::iterator i = g[v].begin(); i != g[v].end(); i++)//идем по дорогам, идущим из вершины
  32.         {
  33.             if (i->yy.xx)//если путь не юзался на первом этапе работы программы
  34.             {
  35.                 d[i->xx] = d[v] = pr[i->xx] = pr[v] = -1;//делаем дистанцию до нее равной -1 и говорим, что инфа от остальных предков не нужна
  36.                 continue;
  37.             }
  38.             else i->yy.xx = 1;//иначе помечаем дорогу как пройденную на первом этапе
  39.             if (pr[v] <= 0)//если все предки отчитались или оно -1, как повествует костыль чуть выше
  40.             {
  41.                 d[i->xx] = add(d[i->xx], d[v]);//пересчитываем расстояние до соседа
  42.                 pr[i->xx]--;//уменьшаем количество неотчитавшихся предков
  43.                 if (!used[i->xx])//если вершина еще не была в очереди, то добавляем ее туда
  44.                 {
  45.                     q[h++] = i->xx;
  46.                     h %= md;
  47.                     used[i->xx] = 1;
  48.                 }
  49.                 debt[v] = 0;//говорим, что вершина никому ничего не должна
  50.             }
  51.             else
  52.             {
  53.                 debt[v] = 1;//говорим, что должна
  54.                 q[h++] = i->xx;
  55.                 h %= md;
  56.             }
  57.         }
  58.     }
  59.     h = t = 0;//очищение очереди
  60.     q[h++] = 0;
  61.     used[0] = 1;
  62.     for (; h != t;)
  63.     {
  64.         v = q[t++];
  65.         t %= md;
  66.         if (pr[v] > 0) continue;//если у  нее есть неотчитавшиеся предки, то она нам пока не нужна
  67.         for (vector<pair<int, pair<bool, bool> > >::iterator i = g[v].begin(); i != g[v].end(); i++)//идем  по соседям
  68.         {
  69.             if (debt[v]) d[i->xx] = add(d[i->xx], d[v]);//если текущая вершина должна своим потомкам, то отдаем долг
  70.             if (!(i->yy.yy))//если путь во второй раз не юзался, то юзаем его
  71.             {
  72.                 q[h++] = i->xx;
  73.                 h %= md;
  74.                 i->yy.yy = 1;
  75.                 pr[i->xx]--;
  76.             }
  77.         }
  78.         debt[v] = 0;// делаем вершину не должной никому
  79.     }
  80.     for (int i = 1; i < n; i++) printf("%d\n", d[i]);//вывод ответа
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement