fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int INF = 1e9;
  5.  
  6. struct DSU {
  7.     vector<int> p, sz;
  8.     DSU(int n): p(n+1), sz(n+1,1) {
  9.         iota(p.begin(), p.end(), 0);
  10.     }
  11.     int find(int x){ return p[x]==x? x : p[x]=find(p[x]); }
  12.     void unite(int a,int b){
  13.         a=find(a); b=find(b);
  14.         if(a==b) return;
  15.         if (sz[a]<sz[b]) swap(a,b);
  16.         p[b]=a; sz[a]+=sz[b];
  17.     }
  18. };
  19.  
  20. int main(){
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(NULL);
  23.  
  24.     int n, m;
  25.     cin >> n >> m;
  26.     DSU dsu(n);
  27.     for(int i=0,u,v; i<m; i++){
  28.         cin >> u >> v;
  29.         dsu.unite(u, v);
  30.     }
  31.     // Đếm kích thước các component
  32.     unordered_map<int,int> freq;
  33.     for(int i=1; i<=n; i++){
  34.         freq[ dsu.find(i) ]++;
  35.     }
  36.     // Gom thành vector (size, count)
  37.     vector<pair<int,int>> items;
  38.     {
  39.         unordered_map<int,int> cnt;
  40.         for(auto &kv: freq){
  41.             cnt[ kv.second ]++;
  42.         }
  43.         for(auto &kv: cnt){
  44.             items.emplace_back(kv.first, kv.second);
  45.         }
  46.     }
  47.     // DP knapsack
  48.     vector<int> dp(n+1, INF);
  49.     dp[0]=0;
  50.     for(auto &it: items){
  51.         int s = it.first, c = it.second;
  52.         // xử lý bounded knapsack tối ưu
  53.         for(int r=0; r<s; ++r){
  54.             deque<pair<int,int>> dq;
  55.             for(int k=0, j=r; j<=n; ++k, j+=s){
  56.                 int val = dp[j] - k;
  57.                 // loại bỏ quá giới hạn c
  58.                 if(!dq.empty() && dq.front().first < k - c)
  59.                     dq.pop_front();
  60.                 // duy trì deque tăng dần theo val
  61.                 while(!dq.empty() && dq.back().second >= val)
  62.                     dq.pop_back();
  63.                 dq.emplace_back(k, val);
  64.                 // cập nhật dp[j]
  65.                 dp[j] = dq.front().second + k;
  66.             }
  67.         }
  68.     }
  69.     // In kết quả
  70.     for(int i=1; i<=n; i++){
  71.         if(dp[i] <= n) cout << dp[i]-1;
  72.         else cout << -1;
  73.         if(i<n) cout << ' ';
  74.     }
  75.     cout << '\n';
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/4BWEEb
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (clang 8.0)

					

					

						
created:
								
						
1 day 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!