求 C 题简单方法

#include<iostream>
#include<vector>
#include<queue>
#include<set>

using namespace std;

const int N = 3e3 + 10, M = 1e6 + 10;
int t, n, x, l[N], p[N]; bool vis[M];
vector<int> a[N], ls, ans;

struct pii{
	int l, i;
	
	bool operator < (const pii & o) const{
		return l > o.l;
	}
};

priority_queue<pii> pq, pq2;
set<int> st;

int main(){
	cin >> t;
	while(t--){
		cin >> n; ans.clear();
		for(int i = 1; i <= n; i++){
			cin >> l[i]; a[i].clear();
			for(int j = 1; j <= l[i]; j++){
				cin >> x; vis[x] = 0;
				a[i].push_back(x);
			}
			p[i] = a[i].size()-1;
			pq.push({a[i].back(), i});
		}
		while(pq.size()){
			int nl = pq.top().l;
			while(pq.size() && pq.top().l == nl){
				st.insert(pq.top().i);
				pq.pop();
			}
//			cout << nl << '\n';
			int mn, mnn; bool fg = 1;
			while(st.size() > 1){
				mn = 1e9;
				for(int i: st){
					mn = min(mn, a[i][p[i]]);
				}
				vis[mn] = 1;
				for(int i: st){
					if(a[i][p[i]] != mn){
						ls.push_back(i);
						pq.push({a[i][p[i]], i});
					}
					else{
						while(p[i] >= 0 && vis[a[i][p[i]]]) p[i]--;
						if(p[i] < 0){
							ls.push_back(i);
							fg = 0;
						}
					}
				}
				for(int i: ls) st.erase(i);
				ls.clear();
				ans.push_back(mn);
				if(fg == 0) break;
			}
			if(st.size() && fg){
				x = *st.begin();
//				cout << x << '\n';
				for(int i = p[x]; i >= 0; i--){
					if(vis[a[x][i]] == 0){
						vis[a[x][i]] = 1;
						ans.push_back(a[x][i]);
					}
				}
				st.clear();
			}
			if(!fg){
				for(int i: st) pq.push({a[i][p[i]], i});
			}
//			for(int i: ans) cout << i << ' ';
//			cout << '\n';
//			cout << pq.size() << '\n';
			while(pq.size()){
				pii tp = pq.top(); pq.pop();
				while(p[tp.i] >= 0 && vis[a[tp.i][p[tp.i]]]){
					p[tp.i]--;
				}
				if(p[tp.i] >= 0) pq2.push({a[tp.i][p[tp.i]], tp.i});
			}
			while(pq2.size()){
				pq.push(pq2.top());
				pq2.pop();
			}
//			cout << pq.size() << '\n';
		}
		for(int i: ans) cout << i << ' ';
		cout << '\n';
	}
	return 0;
}