fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const long long N = 1000005;
  5. long long n, k, edge[N], edge2[N], depth[N], day = 0, worked = 0;
  6. vector<int> cn[N];
  7. vector<int> topo;
  8. #define NAME "lmao"
  9. int main()
  10. {
  11.     ios::sync_with_stdio(false);
  12.     cin.tie(NULL);
  13.     cout.tie(NULL);
  14.     if (fopen(NAME ".inp", "r"))
  15.     {
  16.         freopen(NAME ".inp", "r", stdin);
  17.         freopen(NAME ".out", "w", stdout);
  18.     }
  19.     cin >> n >> k;
  20.     for (int i = 1; i <= n; ++i)
  21.     {
  22.         int x, y;
  23.         cin >> x;
  24.         edge[i] = 0;
  25.         for (int j = 0; j < x; ++j)
  26.         {
  27.             cin >> y;
  28.             cn[y].push_back(i);
  29.             ++edge[i];
  30.         }
  31.     }
  32.     for (int i = 1; i <= n; ++i)
  33.     {
  34.         edge2[i] = edge[i];
  35.     }
  36.     queue<int> q;
  37.     for (int i = 1; i <= n; ++i)
  38.     {
  39.         if (edge2[i] == 0)
  40.         {
  41.             q.push(i);
  42.         }
  43.     }
  44.     while (!q.empty())
  45.     {
  46.         int u = q.front();
  47.         q.pop();
  48.         topo.push_back(u);
  49.         for (int v : cn[u])
  50.         {
  51.             if (--edge2[v] == 0)
  52.             {
  53.                 q.push(v);
  54.             }
  55.         }
  56.     }
  57.     if (topo.size() < n)
  58.     {
  59.         cout << -1;
  60.         return 0;
  61.     }
  62.     for (int u : topo)
  63.         depth[u] = 1;
  64.     for (int i = n - 1; i >= 0; --i)
  65.     {
  66.         int u = topo[i];
  67.         for (int v : cn[u])
  68.         {
  69.             depth[u] = max(depth[u], depth[v] + 1);
  70.         }
  71.     }
  72.     for (int i = 1; i <= n; ++i)
  73.     {
  74.         edge2[i] = edge[i];
  75.     }
  76.     priority_queue<pair<long long, int>> pq;
  77.     for (int i = 1; i <= n; ++i)
  78.     {
  79.         if (edge2[i] == 0)
  80.         {
  81.             pq.push({depth[i], i});
  82.         }
  83.     }
  84.     long long done = 0;
  85.     while (done < n)
  86.     {
  87.         if (pq.empty())
  88.         {
  89.             cout << -1;
  90.             return 0;
  91.         }
  92.         ++day;
  93.         worked = 0;
  94.         vector<pair<long long, int>> temp;
  95.         while (worked < k && !pq.empty())
  96.         {
  97.             auto [d, u] = pq.top();
  98.             pq.pop();
  99.             ++done;
  100.             ++worked;
  101.             for (int v : cn[u])
  102.             {
  103.                 if (--edge2[v] == 0)
  104.                 {
  105.                     temp.emplace_back(depth[v], v);
  106.                 }
  107.             }
  108.         }
  109.         for (auto &pr : temp)
  110.         {
  111.             pq.push(pr);
  112.         }
  113.     }
  114.     cout << day;
  115. }
  116.  
Success #stdin #stdout 0.01s 27512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vOOUVP
language:
C++14 (gcc 8.3)
created:
6 hours 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!