Advertisement
Dang_Quan_10_Tin

teamup

Dec 15th, 2020
184
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.06 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <algorithm>
  5. #define task ""
  6.  
  7. using namespace std;
  8. using ll = long long;
  9.  
  10. const int N = 3e5 + 2;
  11. vector<int> f[N], s[N], cnt[N];
  12. vector<int> adj[N];
  13. int a[N], id[N], par[N];
  14. int m, n, p;
  15.  
  16. void Read(){
  17.     cin >> n >> m >> p;
  18.     for (int i = 1; i <= m; ++i){
  19.         int v;
  20.         cin >> v;
  21.         s[i].resize(v);
  22.         for(auto &j : s[i])
  23.             cin >> j;
  24.         id[i] = i;
  25.     }
  26.     for (int i = 1; i <= p; ++i){
  27.         cin >> a[i];
  28.         cnt[a[i]].push_back(i);
  29.     }
  30.     sort(id + 1, id + m + 1, [&](const int &x, const int &y) {
  31.         return s[x].size() < s[y].size();
  32.     });
  33.     for (int i = 1; i <= m; ++i)
  34.         for (auto j : s[id[i]])
  35.             f[j].push_back(id[i]);
  36. }
  37.  
  38. inline void Unique(vector<int> &s){
  39.     sort(s.begin(), s.end());
  40.     s.resize(unique(s.begin(), s.end()) - s.begin());
  41. }
  42.  
  43. bool Check(vector<int> ans){
  44.     vector<int> v;
  45.     for(auto i : ans)
  46.         for(auto j : s[i])
  47.             v.push_back(j);
  48.     Unique(v);
  49.     return v.size() == n;
  50. }
  51.  
  52. void BuildDAG(){
  53.     for (int i = 1; i <= n; ++i)
  54.         for(auto j : f[i]){
  55.             int l = 0, m, h = (int)f[i].size() - 1;
  56.             while(l <= h){
  57.                 m = (l + h) / 2;
  58.                 if(s[f[i][m]].size() <= s[j].size())
  59.                     l = m + 1;
  60.                 else
  61.                     h = m - 1;
  62.             }
  63.             if(l < f[i].size()){
  64.                 par[j] = f[i][l];
  65.                 adj[f[i][l]].push_back(j);
  66.             }
  67.         }
  68.     //for (int i = 1; i <= m; ++i)
  69.     //    cout << i << ": " << a[i] << "\n";
  70. }
  71.  
  72. void Solve(){
  73.     vector<int> ans;
  74.     vector<vector<int>> res;
  75.     int num(0);
  76.     for (int i = 1; i <= m; ++i){
  77.         Unique(adj[i]);
  78.         if(par[i] == 0 && cnt[i].size() != 0){
  79.             num += s[i].size();
  80.             ans.push_back(i);
  81.         }
  82.     }
  83.     do{
  84.         if(num != n)
  85.             break;
  86.         vector<int> tmp, now;
  87.         for(auto i : ans){
  88.             now.push_back(cnt[i].back());
  89.             cnt[i].pop_back();
  90.             if(cnt[i].empty()){
  91.                 tmp.push_back(i);
  92.                 num -= s[i].size();
  93.             }
  94.         }
  95.         res.push_back(now);
  96.         for (int i = (int)ans.size() - 1; ~i; --i)
  97.             if(cnt[ans[i]].empty()){
  98.                 ans[i] = ans.back();
  99.                 ans.pop_back();
  100.             }
  101.         for(auto i : tmp)
  102.             for(auto j : adj[i])
  103.                 if(cnt[j].size()){
  104.                     ans.push_back(j);
  105.                     num += s[j].size();
  106.                 }
  107.     } while (ans.size());
  108.     cout << res.size() << "\n";
  109.     for(auto i : res){
  110.         cout << i.size() << " ";
  111.         for(auto j : i)
  112.             cout << j << " ";
  113.         cout << "\n";
  114.     }
  115. }
  116.  
  117. int32_t main(){
  118.     if(fopen(task".INP", "r")){
  119.         freopen(task".INP", "r", stdin);
  120.     freopen(task".OUT", "w", stdout);
  121.     }
  122.     ios_base::sync_with_stdio(0);
  123.     cin.tie(0);
  124.     cout.tie(0);
  125.     Read();
  126.     BuildDAG();
  127.     Solve();
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement