Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <vector>
- #include <algorithm>
- #define task ""
- using namespace std;
- using ll = long long;
- const int N = 3e5 + 2;
- vector<int> f[N], s[N], cnt[N];
- vector<int> adj[N];
- int a[N], id[N], par[N];
- int m, n, p;
- void Read(){
- cin >> n >> m >> p;
- for (int i = 1; i <= m; ++i){
- int v;
- cin >> v;
- s[i].resize(v);
- for(auto &j : s[i])
- cin >> j;
- id[i] = i;
- }
- for (int i = 1; i <= p; ++i){
- cin >> a[i];
- cnt[a[i]].push_back(i);
- }
- sort(id + 1, id + m + 1, [&](const int &x, const int &y) {
- return s[x].size() < s[y].size();
- });
- for (int i = 1; i <= m; ++i)
- for (auto j : s[id[i]])
- f[j].push_back(id[i]);
- }
- inline void Unique(vector<int> &s){
- sort(s.begin(), s.end());
- s.resize(unique(s.begin(), s.end()) - s.begin());
- }
- bool Check(vector<int> ans){
- vector<int> v;
- for(auto i : ans)
- for(auto j : s[i])
- v.push_back(j);
- Unique(v);
- return v.size() == n;
- }
- void BuildDAG(){
- for (int i = 1; i <= n; ++i)
- for(auto j : f[i]){
- int l = 0, m, h = (int)f[i].size() - 1;
- while(l <= h){
- m = (l + h) / 2;
- if(s[f[i][m]].size() <= s[j].size())
- l = m + 1;
- else
- h = m - 1;
- }
- if(l < f[i].size()){
- par[j] = f[i][l];
- adj[f[i][l]].push_back(j);
- }
- }
- //for (int i = 1; i <= m; ++i)
- // cout << i << ": " << a[i] << "\n";
- }
- void Solve(){
- vector<int> ans;
- vector<vector<int>> res;
- int num(0);
- for (int i = 1; i <= m; ++i){
- Unique(adj[i]);
- if(par[i] == 0 && cnt[i].size() != 0){
- num += s[i].size();
- ans.push_back(i);
- }
- }
- do{
- if(num != n)
- break;
- vector<int> tmp, now;
- for(auto i : ans){
- now.push_back(cnt[i].back());
- cnt[i].pop_back();
- if(cnt[i].empty()){
- tmp.push_back(i);
- num -= s[i].size();
- }
- }
- res.push_back(now);
- for (int i = (int)ans.size() - 1; ~i; --i)
- if(cnt[ans[i]].empty()){
- ans[i] = ans.back();
- ans.pop_back();
- }
- for(auto i : tmp)
- for(auto j : adj[i])
- if(cnt[j].size()){
- ans.push_back(j);
- num += s[j].size();
- }
- } while (ans.size());
- cout << res.size() << "\n";
- for(auto i : res){
- cout << i.size() << " ";
- for(auto j : i)
- cout << j << " ";
- cout << "\n";
- }
- }
- int32_t main(){
- if(fopen(task".INP", "r")){
- freopen(task".INP", "r", stdin);
- freopen(task".OUT", "w", stdout);
- }
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- Read();
- BuildDAG();
- Solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement