fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
  6. template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8. const int MAXLOG = 20;
  9.  
  10. struct dsu
  11. {
  12. 	int sz;
  13. 	vector<int> par, psz;
  14.  
  15. 	void init(int n)
  16. 	{
  17. 		sz = n;
  18. 		par.assign(sz + 1, 0);
  19. 		psz.assign(sz + 1, 0);
  20. 		for(int i = 0; i <= sz; i++)
  21. 			par[i] = i, psz[i] = 1;
  22. 	}
  23.  
  24. 	int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
  25.  
  26. 	bool connected(int x, int y) { return root(x) == root(y); }
  27.  
  28. 	void unite(int x, int y)
  29. 	{
  30. 		x = root(x), y = root(y);
  31. 		if(psz[x] > psz[y]) swap(x, y);
  32. 		par[x] = y, psz[y] += psz[x]; 
  33. 	}
  34. };
  35.  
  36. int n = 0, q;
  37. vector<int> G[MAXN];
  38. string type[MAXN];
  39. int argg[MAXN];
  40.  
  41. void read()
  42. {
  43. 	cin >> q;
  44. 	for(int i = 0; i < q; i++)
  45. 	{
  46. 		cin >> type[i] >> argg[i];
  47. 		if(type[i] == "B")
  48. 		{
  49. 			n++;
  50. 			if(argg[i] != -1) 
  51. 			{
  52. 				G[argg[i]].push_back(n);
  53. 				G[n].push_back(argg[i]);
  54. 			}
  55. 		}
  56. 	}
  57. }
  58.  
  59. int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
  60. int par[MAXN][MAXLOG];
  61.  
  62. void dfs_lca(int u)
  63. {
  64. 	st[u] = ++dfs_time;
  65. 	for(int i = 1; i < MAXLOG; i++)
  66. 		par[u][i] = par[par[u][i - 1]][i - 1];
  67.  
  68. 	for(int v: G[u])
  69. 		if(v != par[u][0])
  70. 		{
  71. 			par[v][0] = u;
  72. 			dep[v] = dep[u] + 1;
  73. 			dfs_lca(v);
  74. 		}
  75.  
  76. 	en[u] = dfs_time;
  77. }
  78.  
  79. inline bool upper(int u, int v) { return st[u] <= st[v] && en[v] <= en[u]; }
  80.  
  81. int lca(int u, int v)
  82. {
  83. 	if(upper(u, v)) return u;
  84. 	if(upper(v, u)) return v;
  85.  
  86. 	int a = u;
  87. 	for(int i = MAXLOG - 1; i >= 0; i--)
  88. 		if(!upper(par[a][i], v))
  89. 			a = par[a][i];
  90.  
  91. 	return par[a][0];
  92. }
  93.  
  94. int parent(int u, int up)
  95. {
  96. 	int a = u;
  97. 	for(int i = MAXLOG - 1; i >= 0; i--)
  98. 		if(up & (1 << i))
  99. 			a = par[a][i];
  100.  
  101. 	return a;
  102. }
  103.  
  104. void lca_precompute(int root)
  105. {
  106. 	for(int i = 0; i < MAXLOG; i++)
  107.         par[root][i] = root;
  108.  
  109. 	dfs_time = 0;
  110. 	dfs_lca(root);
  111. }
  112.  
  113. bool used[MAXN];
  114. dsu d;
  115.  
  116. void dfs_check(int u)
  117. {
  118. 	used[u] = 1;
  119. 	for(int v: G[u])
  120. 		if(!used[v])
  121. 			dfs_check(v);
  122. }
  123.  
  124. int d1[MAXN], d2[MAXN];
  125. int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }
  126.  
  127. void merge(int a, int b)
  128. {
  129. 	d.unite(a, b);
  130.  
  131. 	vector<int> cands = {d1[a], d2[a], d1[b], d2[b]};
  132. 	int root = d.root(a);
  133.  
  134. 	int mx = 0;
  135. 	for(int i = 0; i < (int)cands.size(); i++)
  136. 		for(int j = i + 1; j < (int)cands.size(); j++)
  137. 		{
  138. 			int d = dist(cands[i], cands[j]);
  139. 			if(d > mx)
  140. 			{
  141. 				mx = d;
  142. 				d1[root] = cands[i];
  143. 				d2[root] = cands[j];
  144. 			}
  145. 		}
  146. }
  147.  
  148. void solve()
  149. {
  150. 	for(int i = 1; i <= n; i++)
  151. 		if(!used[i])
  152. 		{
  153. 			lca_precompute(i);
  154. 			dfs_check(i);
  155. 		}
  156.  
  157. 	d.init(n);
  158. 	for(int i = 1; i <= n; i++)
  159. 		d1[i] = i, d2[i] = i;
  160.  
  161. 	int c_ver = 0;
  162. 	for(int i = 0; i < q; i++)
  163. 	{
  164. 		if(type[i] == "B")
  165. 		{
  166. 			c_ver++;
  167. 			if(argg[i] != -1)
  168. 				merge(d.root(argg[i]), d.root(c_ver));
  169. 		}
  170. 		else
  171. 		{
  172. 			int u = argg[i], c = d.root(u);
  173. 			cout << max(dist(u, d1[c]), dist(u, d2[c])) << endl;
  174. 		}
  175. 	}
  176. }
  177.  
  178. int main()
  179. {
  180. 	freopen("newbarn.in", "r", stdin);
  181. 	freopen("newbarn.out", "w", stdout);
  182. 	ios_base::sync_with_stdio(false);
  183. 	cin.tie(NULL);
  184.  
  185. 	read();
  186. 	solve();
  187. 	return 0;
  188. }
  189.  
  190.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#include <bits/stdc++.h>
^
Main.java:1: error: class, interface, or enum expected
#include <bits/stdc++.h>
         ^
Main.java:2: error: illegal character: '#'
#define endl '\n'
^
Main.java:5: error: class, interface, or enum expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
^
Main.java:5: error: '{' expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                ^
Main.java:5: error: '{' expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                          ^
Main.java:5: error: <identifier> expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                ^
Main.java:5: error: ';' expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                  ^
Main.java:5: error: illegal start of type
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                   ^
Main.java:5: error: <identifier> expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                    ^
Main.java:5: error: ';' expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                          ^
Main.java:5: error: illegal start of type
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                              ^
Main.java:5: error: ';' expected
template<class T, class T2> inline void chkmax(T &x, const T2 &y) { if(x < y) x = y; }
                                                                ^
Main.java:6: error: illegal start of type
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
         ^
Main.java:6: error: <identifier> expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                 ^
Main.java:6: error: <identifier> expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                          ^
Main.java:6: error: <identifier> expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                  ^
Main.java:6: error: invalid method declaration; return type required
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                        ^
Main.java:6: error: <identifier> expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                ^
Main.java:6: error: ';' expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                  ^
Main.java:6: error: illegal start of type
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                   ^
Main.java:6: error: <identifier> expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                    ^
Main.java:6: error: ';' expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                          ^
Main.java:6: error: illegal start of type
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                              ^
Main.java:6: error: ';' expected
template<class T, class T2> inline void chkmin(T &x, const T2 &y) { if(x > y) x = y; }
                                                                ^
Main.java:7: error: illegal start of type
const int MAXN = (1 << 20);
^
Main.java:7: error: ';' expected
const int MAXN = (1 << 20);
     ^
Main.java:7: error: <identifier> expected
const int MAXN = (1 << 20);
              ^
Main.java:8: error: illegal start of type
const int MAXLOG = 20;
^
Main.java:8: error: ';' expected
const int MAXLOG = 20;
     ^
Main.java:8: error: <identifier> expected
const int MAXLOG = 20;
                ^
Main.java:10: error: ';' expected
struct dsu
          ^
Main.java:15: error: illegal start of expression
	void init(int n)
	^
Main.java:15: error: ';' expected
	void init(int n)
	         ^
Main.java:15: error: ';' expected
	void init(int n)
	               ^
Main.java:21: error: ';' expected
			par[i] = i, psz[i] = 1;
			          ^
Main.java:24: error: ';' expected
	int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
	        ^
Main.java:24: error: ';' expected
	int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
	              ^
Main.java:26: error: ';' expected
	bool connected(int x, int y) { return root(x) == root(y); }
	              ^
Main.java:26: error: <identifier> expected
	bool connected(int x, int y) { return root(x) == root(y); }
	                     ^
Main.java:26: error: not a statement
	bool connected(int x, int y) { return root(x) == root(y); }
	                          ^
Main.java:26: error: ';' expected
	bool connected(int x, int y) { return root(x) == root(y); }
	                           ^
Main.java:28: error: illegal start of expression
	void unite(int x, int y)
	^
Main.java:28: error: ';' expected
	void unite(int x, int y)
	          ^
Main.java:28: error: <identifier> expected
	void unite(int x, int y)
	                 ^
Main.java:28: error: not a statement
	void unite(int x, int y)
	                      ^
Main.java:28: error: ';' expected
	void unite(int x, int y)
	                       ^
Main.java:30: error: ';' expected
		x = root(x), y = root(y);
		           ^
Main.java:32: error: ';' expected
		par[x] = y, psz[y] += psz[x]; 
		          ^
Main.java:37: error: ']' expected
vector<int> G[MAXN];
              ^
Main.java:37: error: illegal start of type
vector<int> G[MAXN];
                  ^
Main.java:37: error: <identifier> expected
vector<int> G[MAXN];
                   ^
Main.java:37: error: ';' expected
vector<int> G[MAXN];
                    ^
Main.java:38: error: ']' expected
string type[MAXN];
            ^
Main.java:38: error: ';' expected
string type[MAXN];
                ^
Main.java:39: error: ']' expected
int argg[MAXN];
         ^
Main.java:39: error: illegal start of type
int argg[MAXN];
             ^
Main.java:39: error: <identifier> expected
int argg[MAXN];
              ^
Main.java:39: error: ';' expected
int argg[MAXN];
               ^
Main.java:41: error: invalid method declaration; return type required
void read()
     ^
Main.java:43: error: not a statement
	cin >> q;
	    ^
Main.java:46: error: not a statement
		cin >> type[i] >> argg[i];
		               ^
Main.java:59: error: ']' expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
        ^
Main.java:59: error: illegal start of type
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
            ^
Main.java:59: error: <identifier> expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
             ^
Main.java:59: error: ';' expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
              ^
Main.java:59: error: illegal start of type
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
                 ^
Main.java:59: error: ';' expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
                      ^
Main.java:59: error: ']' expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
                            ^
Main.java:59: error: ';' expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
                                ^
Main.java:59: error: <identifier> expected
int dep[MAXN], st[MAXN], en[MAXN], dfs_time = 0;
                                           ^
Main.java:60: error: ']' expected
int par[MAXN][MAXLOG];
        ^
Main.java:60: error: illegal start of type
int par[MAXN][MAXLOG];
            ^
Main.java:60: error: <identifier> expected
int par[MAXN][MAXLOG];
             ^
Main.java:60: error: ';' expected
int par[MAXN][MAXLOG];
              ^
Main.java:60: error: illegal start of type
int par[MAXN][MAXLOG];
                    ^
Main.java:60: error: <identifier> expected
int par[MAXN][MAXLOG];
                     ^
Main.java:60: error: ';' expected
int par[MAXN][MAXLOG];
                      ^
Main.java:62: error: invalid method declaration; return type required
void dfs_lca(int u)
     ^
Main.java:79: error: ';' expected
inline bool upper(int u, int v) { return st[u] <= st[v] && en[v] <= en[u]; }
           ^
Main.java:79: error: invalid method declaration; return type required
inline bool upper(int u, int v) { return st[u] <= st[v] && en[v] <= en[u]; }
            ^
Main.java:113: error: ']' expected
bool used[MAXN];
          ^
Main.java:113: error: illegal start of type
bool used[MAXN];
              ^
Main.java:113: error: <identifier> expected
bool used[MAXN];
               ^
Main.java:113: error: ';' expected
bool used[MAXN];
                ^
Main.java:114: error: <identifier> expected
dsu d;
     ^
Main.java:124: error: ']' expected
int d1[MAXN], d2[MAXN];
       ^
Main.java:124: error: illegal start of type
int d1[MAXN], d2[MAXN];
           ^
Main.java:124: error: <identifier> expected
int d1[MAXN], d2[MAXN];
            ^
Main.java:124: error: ';' expected
int d1[MAXN], d2[MAXN];
             ^
Main.java:124: error: illegal start of type
int d1[MAXN], d2[MAXN];
                ^
Main.java:124: error: ';' expected
int d1[MAXN], d2[MAXN];
                     ^
Main.java:159: error: ';' expected
		d1[i] = i, d2[i] = i;
		         ^
Main.java:173: error: not a statement
			cout << max(dist(u, d1[c]), dist(u, d2[c])) << endl;
			                                            ^
Main.java:182: error: not a statement
	ios_base::sync_with_stdio(false);
	^
Main.java:182: error: ';' expected
	ios_base::sync_with_stdio(false);
	                         ^
Main.java:188: error: reached end of file while parsing
}
 ^
97 errors
stdout
copy 
Standard output is empty
https://ideone.com/tfVpDY
language:
Java (HotSpot 12)
created:
6 years 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!