fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(x) x.begin(), x.end()
  5. #define pb push_back
  6. #define FOR(i,a,b) for(int i = (a); i < (b); ++i)
  7. #define ROF(i,a,b) for(int i = (a); i >= (b); --i)
  8. #define trav(a,x) for(auto& a: x)
  9. #define sz(x) (int)x.size()
  10. template<class T> bool ckmax(T& a, const T& b){return a<b?a=b,1:0;}
  11. template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for(auto &x : a) out << x << ' '; return out;};
  12.  
  13. void solve() {
  14. 	int n; cin >> n;
  15. 	vector<vector<int>> g(n), relevant;
  16. 	int max_k = 0;
  17. 	FOR(i,0,n){
  18. 		int k; cin >> k;
  19. 		g[i].resize(k);
  20. 		ckmax(max_k, k);
  21. 		FOR(j,0,k){
  22. 			cin >> g[i][j];
  23. 			if(sz(relevant) == j) relevant.pb({});
  24. 			relevant[j].pb(i);
  25. 		}
  26. 	}
  27. 	vector<int> lex_min(max_k), rank(n, -1);
  28. 	ROF(i,max_k-1,0){
  29. 		vector<array<int, 3>> cur;
  30. 		trav(j, relevant[i]){
  31. 			cur.pb({g[j][i], rank[j], j});
  32. 		}
  33. 		sort(all(cur));
  34. 		lex_min[i] = cur[0][2];
  35. 		int rk = 0;
  36. 		trav(j, cur) rank[j[2]] = rk++;
  37. 	}
  38. 	vector<int> ans;
  39. 	while(sz(ans) < max_k){
  40. 		int tmp = sz(ans);
  41. 		auto& v = g[lex_min[tmp]];
  42. 		FOR(i,tmp,sz(v)) ans.pb(v[i]);
  43. 	}
  44. 	assert(sz(ans) == max_k);
  45. 	cout << ans << "\n";
  46. }
  47.  
  48. signed main() {
  49. 	cin.tie(0) -> sync_with_stdio(0);
  50. 	int t = 1;
  51. 	cin >> t;
  52. 	for(int test = 1; test <= t; test++){
  53. 		solve();
  54. 	}
  55. }
  56.  
  57. /*   /\_/\
  58. *   (= ._.)
  59. *   / >  \>
  60. */
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/845cR0
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
15 days 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!