fork download 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3.  
  4. #define fi first
  5. #define se second
  6. #define pii pair<int,int> 
  7. #define all(x) x.begin(), x.end()
  8. #define sz(x) (int)x.size()
  9. #define pb push_back
  10. #define ll long long
  11.  
  12. const int MAXN = 200005;
  13. const int MAX_COLORS = 400005; // N + Q
  14.  
  15. int N, Q;
  16. vector<int> adj[MAXN];
  17. int color[MAXN];
  18. vector<int> vertices_of_color[MAX_COLORS];
  19. int dist[MAXN];
  20.  
  21. void bfs() {
  22.     for (int i = 1; i <= N; ++i) {
  23.         dist[i] = -1;
  24.     }
  25.     queue<int> q;
  26.  
  27.     dist[1] = 0;
  28.     q.push(1);
  29.  
  30.     while (!q.empty()) {
  31.         int u = q.front();
  32.         q.pop();
  33.  
  34.         for (int v : adj[u]) {
  35.             if (dist[v] == -1) {
  36.                 dist[v] = dist[u] + 1;
  37.                 q.push(v);
  38.             }
  39.         }
  40.     }
  41. }
  42.  
  43. signed main(){
  44.     ios_base::sync_with_stdio(NULL);
  45.     cin.tie(NULL);
  46.     if(fopen("TASK.INP", "r")){
  47.         freopen("TASK.INP", "r", stdin);
  48.         freopen("TASK.ANS", "w", stdout);
  49.     }
  50.  
  51.     cin >> N >> Q;
  52.     for (int i = 1; i <= N; ++i) {
  53.         cin >> color[i];
  54.         vertices_of_color[color[i]].pb(i);
  55.     }
  56.  
  57.     for (int i = 0; i < Q; ++i) {
  58.         int type;
  59.         cin >> type;
  60.         if (type == 1) {
  61.             int x, y;
  62.             cin >> x >> y;
  63.             if (x == y) continue; // Tối ưu nhỏ, tránh tự nối
  64.             for (int u : vertices_of_color[x]) {
  65.                 for (int v : vertices_of_color[y]) {
  66.                     adj[u].pb(v);
  67.                     adj[v].pb(u);
  68.                 }
  69.             }
  70.         } else {
  71.             int u, v;
  72.             cin >> u >> v;
  73.             if (u == v) continue;
  74.  
  75.             // Chuyển tất cả đỉnh từ màu u sang màu v
  76.             for (int node : vertices_of_color[u]) {
  77.                 color[node] = v;
  78.                 vertices_of_color[v].pb(node);
  79.             }
  80.             vertices_of_color[u].clear();
  81.         }
  82.     }
  83.  
  84.     bfs();
  85.  
  86.     for (int i = 2; i <= N; ++i) {
  87.         cout << dist[i] << (i == N ? "" : " ");
  88.     }
  89.     cout << "\n";
  90.  
  91. }
Success #stdin #stdout 0.01s 18500KB
comments (?)
stdin 
Standard input is empty
stdout 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			


			                        
			
			

				

	
					
					 https://ideone.com/7G1FO2
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
13 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!