fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef ANI
  5. #include "D:/DUSTBIN/local_inc.h"
  6. #else
  7. #define dbg(...) 0
  8. #endif
  9.  
  10. class LCA{
  11. public:
  12. 	int MB=20,N,ROOT;
  13. 	vector<vector<int>> up,e;
  14. 	vector<int> depth;
  15. 	void dfs(int cur,int par) {
  16. 		up[cur][0]=par;
  17. 		for(int bit=1;bit<=MB;bit++) {
  18. 			up[cur][bit]=up[up[cur][bit-1]][bit-1];
  19. 		}
  20. 		for(int node:e[cur]) {
  21. 			if(node!=par) {
  22. 				depth[node]=depth[cur]+1;
  23. 				dfs(node,cur);
  24.  
  25. 			}
  26. 		}
  27. 	}
  28. 	LCA(vector<vector<int>> _,int root=0){
  29. 		e=_; N=e.size(); ROOT=root;
  30. 		up=vector<vector<int>>(N,vector<int>(MB+1,0));
  31. 		depth=vector<int>(N,0); dfs(ROOT,ROOT);
  32. 	}
  33. 	LCA() {}
  34. 	int kth(int node,int k) {
  35. 		if(k>depth[node]) return -1;
  36. 		int bit=0;
  37. 		while(k) {
  38. 			if(k&1) node=up[node][bit];
  39. 			k>>=1; bit++;
  40. 		}
  41. 		return node;
  42. 	}
  43. 	int getlca(int u, int v) {
  44. 		if(depth[u]<depth[v]) swap(u, v);
  45. 		for(int bit=MB;bit>=0;bit--) 
  46. 			if(depth[u]-(1<<bit)>=depth[v])
  47. 				u=up[u][bit];
  48. 		if(u==v) return u;
  49. 		for(int bit=MB;bit>=0;bit--) 
  50. 			if(up[u][bit]!=up[v][bit])
  51. 				u=up[u][bit],v=up[v][bit];
  52. 		return up[u][0];
  53. 	}
  54. 	int dist(int u,int v) {
  55. 		return depth[u]+depth[v]-2*depth[getlca(u,v)];
  56. 	}
  57. };
  58.  
  59. class dsu{
  60. public:
  61. 	int N;
  62. 	vector<int> par,size;
  63. 	vector<array<int,2>> dd;
  64. 	LCA lc;
  65. 	dsu(int n, LCA lc) {
  66. 		this->lc=lc;
  67. 		N=n;
  68. 		par=size=vector<int>(N,1);
  69. 		dd=vector<array<int,2>>(N);
  70. 		for(int i=0;i<N;i++) {
  71. 			par[i]=i;
  72. 			dd[i]={i,i};
  73. 		}
  74. 	}
  75. 	int find(int u) {
  76. 		return par[u]==u?u:par[u]=find(par[u]);
  77. 	}
  78. 	int join(int u,int v) {
  79. 		u=find(u),v=find(v);
  80. 		if(u==v) return 0;
  81. 		if(size[u]<size[v]) swap(u,v);
  82. 		par[v]=u;
  83. 		size[u]+=size[v];
  84.  
  85.  
  86. 		vector<int> diam={dd[u][0],dd[u][1],dd[v][0],dd[v][1]};
  87. 		int d1=0,d2=0;
  88. 		for(int i=0;i<4;i++) {
  89. 			for(int j=i+1;j<4;j++) {
  90. 				if(lc.dist(diam[i],diam[j]) > lc.dist(diam[d1],diam[d2])) {
  91. 					d1=i; d2=j;
  92. 				}
  93. 			}
  94. 		}
  95.  
  96. 		dd[u]={diam[d1],diam[d2]};
  97. 		return 1;
  98. 	}
  99. };
  100.  
  101. void solve() {
  102. 	int n,m;
  103. 	cin>>n>>m;
  104.  
  105. 	/*
  106. 		for every node suppose we have:
  107. 			dist from root
  108.  
  109. 		now let earlier diameter be D1...D2
  110. 		either this will remain unchanged
  111. 		or D1..cur
  112. 		or D2..cur
  113.  
  114. 		check all these using lca?
  115. 	*/
  116.  
  117. 	vector<vector<int>> e(n),qq(m);
  118.  
  119. 	for(int i=0;i<m;i++) {
  120. 		int t; cin>>t;
  121. 		if(t==1) {
  122. 			int u,v;
  123. 			cin>>u>>v;
  124. 			u--;v--;
  125. 			e[u].push_back(v);
  126. 			e[v].push_back(u);
  127. 			qq[i]={1,u,v};
  128. 		} else {
  129. 			int u; cin>>u; u--;
  130. 			qq[i]={2,u};
  131. 		}
  132. 	}
  133.  
  134. 	// dbg(qq); exit(0);
  135.  
  136. 	dbg(qq);
  137. 	LCA lca(e);
  138.  
  139. 	dsu d(n, lca);
  140.  
  141. 	for(int i=0;i<m;i++) {
  142. 		int t=qq[i][0];
  143. 		if(t==1) {
  144. 			d.join(qq[i][1],qq[i][2]);
  145. 			continue;
  146. 		}
  147. 		int node=qq[i][1];
  148. 		int leader=d.find(node);
  149. 		int d1=d.dd[leader][0],d2=d.dd[leader][1];
  150. 		int dist1=lca.dist(node,d1), dist2=lca.dist(node,d2);
  151. 		cout<<max(dist2,dist1)<<" "<<(dist1>dist2?d1+1:d2+1)<<"\n";
  152. 	}
  153.  
  154. 	cout<<"\n";
  155. }
  156.  
  157. int main() {
  158. 	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  159. 	int t;
  160. 	cin>>t;
  161. 	while(t--) {
  162. 		solve();
  163. 	}	
  164. }
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
2
7 9
1 3 1
1 5 2
2 5
2 2
2 2
1 2 1
1 4 1
1 4 7
1 6 2
9 9
1 3 7
1 5 4
1 1 2
1 9 4
1 8 7
2 3
1 4 2
1 6 2
1 2 3
stdout
copy 
1 2
1 5
1 5

2 8
https://ideone.com/7NGuei
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!