fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <math.h>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <string.h>
  7. #include <set>
  8. #include <map>
  9. #include <bitset>
  10. #include <time.h>
  11. using namespace std;
  12.  
  13. typedef vector <int> vi;
  14.  
  15. #define ll long long
  16. #define pb push_back
  17. #define ld double
  18. #define pld pair <ld, ld>
  19. #define pll pair <ll, ll>
  20. #define fi first
  21. #define pii pair <int, int>
  22. #define se second
  23. #define mp make_pair
  24.  
  25. const int MAXN = 100 * 1000;
  26. const int INF = 1000 * 1000;
  27.  
  28. int cnt[MAXN], pr[MAXN], ind[MAXN], num[MAXN];
  29. int cntt = 0;
  30. vector <int> g[MAXN];
  31. bool is_heavy(int v, int pr)
  32. {
  33. 	return (cnt[v] < cnt[pr]) && (cnt[v] * 2 >= cnt[pr]);
  34. }
  35.  
  36. class tree
  37. {
  38. public:
  39. 	int len;
  40. 	int ne;
  41. 	vector <int> t;
  42. 	vector <int> node;
  43. 	void build(int v)
  44. 		{
  45. 			while (is_heavy(v, pr[v]))
  46. 			{
  47. 				ind[v] = (int)node.size();
  48. 				node.pb(v);
  49. 				num[v] = cntt;
  50. 				v = pr[v];
  51. 			}
  52.  
  53. 			if (v)
  54. 			{
  55. 				ind[v] = (int)node.size();
  56. 				node.pb(v);
  57. 				num[v] = cntt;
  58. 				ne = pr[v];
  59. 			}
  60. 			for (len = 1; len < (int)node.size(); len *= 2);
  61. 			t.assign(2 * len, INF);
  62. 		}
  63.  
  64.  
  65. 	void update(int ind, int v, int l, int r)
  66. 		{
  67. 			if (l == r)
  68. 			{
  69. 				if (t[v] == INF)
  70. 					t[v] = node[v - len];
  71. 				else
  72. 					t[v] = INF;
  73. 				return;
  74. 			}
  75. 			int s = (l + r) / 2;
  76. 			if (ind <= s)
  77. 				update(ind, 2 * v, l, s);
  78. 			else
  79. 				update(ind, 2 * v + 1, s + 1, r);
  80. 			if (t[2 * v] == INF)
  81. 				t[v] = t[2 * v + 1];
  82. 			else
  83. 				t[v] = t[2 * v];
  84. 		}
  85. 	int find(int tl, int tr, int v, int l, int r)
  86. 		{
  87. 			if (tl > tr) return INF;
  88. 			if (tl == l && tr == r)
  89. 				return t[v];
  90. 			int s = (l + r) /s;
  91. 			int vall = find(tl, min(s, tr), 2 * v, l, s);
  92. 			int valr = find(max(tl, s + 1), tr, 2 * v + 1, s + 1, r);
  93. 			if (vall == INF) return valr;
  94. 			return vall;
  95. 		}
  96. };
  97.  
  98. tree t[MAXN];
  99. int dfs(int v, int _pr)
  100. {
  101. 	pr[v] = _pr;
  102. 	cnt[v] = 1;
  103. 	for (int i = 0; i < (int)g[v].size(); i++)
  104. 		if (g[v][i] != _pr)
  105. 			cnt[v] += dfs(g[v][i], v);
  106. 	return cnt[v];
  107. }
  108.  
  109.  
  110. void find_path(int v)
  111. {
  112. 	bool ok = 1;
  113. 	for (int i = 0; i < (int)g[v].size(); i++)
  114. 		if (g[v][i] != pr[v])
  115. 		{
  116. 			if (is_heavy(g[v][i], v))
  117. 				ok = 0;
  118. 			find_path(g[v][i]);
  119. 		}
  120. 	if (ok)
  121. 		t[cntt].build(v), cntt++;
  122. }
  123.  
  124.  
  125. int color[MAXN];
  126. int _type[MAXN * 4],  _v[MAXN * 4];
  127. int main()
  128. {
  129. 	//freopen("subsequences.in", "r", stdin);
  130. 	//freopen("subsequences.out", "w", stdout);
  131. //	freopen("input.txt", "r", stdin);
  132. //	freopen("output.txt", "w", stdout);
  133. 	ios_base::sync_with_stdio(false);
  134. 	int n, q;
  135. 	cin >> n >> q;
  136. 	for (int i = 0; i < n - 1; i++)
  137. 	{
  138. 		int a, b;
  139. 		cin >> a >> b;
  140. 		a--, b--;
  141. 		g[a].pb(b);
  142. 		g[b].pb(a);
  143. 	}
  144. 	for (int i = 0; i < q; i++)
  145. 		cin >> _type[i] >> _v[i];
  146. 	dfs(0, 0);
  147. 	find_path(0);
  148. 	//for (int i = 0; i < cntt; i++)
  149. //	{
  150. //		for (int j = 0; j < (int)t[i].node.size(); j++)
  151. //			cout << t[i].node[j] << " ";
  152. //		cout << endl;
  153. //	}
  154. //	for (int i = 0; i < n; i++)
  155. //		cout << ind[i] << endl;
  156. 	//return 0;
  157. 	for (int i = 0; i < q; i++)
  158. 	{
  159. 		int type = _type[i];
  160. 		int v = _v[i];
  161. 		v--;
  162. 		if (type)
  163. 		{
  164. 			int len = t[num[v]].len;
  165. 			int ans = INF;
  166. 			while (v && ans == INF)
  167. 			{
  168. 				ans = t[num[v]].find(ind[v] + len, len * 2 - 1, 1, len, len * 2 - 1);
  169. 				v = t[num[v]].ne;
  170. 			}
  171. 		    if (ans == INF && color[0]) ans = 0;
  172. 			if (ans == INF)
  173. 				cout << -1;
  174. 			else
  175. 				cout << ans + 1;
  176. 			cout << '\n';
  177. 		}
  178. 		else
  179. 		{
  180. 			color[v] = 1 - color[v];
  181. 			if (v)
  182. 			{
  183. 				int len = t[num[v]].len;
  184. 				t[num[v]].update(ind[v] + len, 1, len, len * 2 - 1);
  185. 			}
  186.  
  187. 		}
  188. 	}
  189. 	return 0;
  190. }
  191.  
  192.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#include <iostream>
^
Main.java:1: error: class, interface, or enum expected
#include <iostream>
         ^
Main.java:2: error: illegal character: '#'
#include <cstdio>
^
Main.java:3: error: illegal character: '#'
#include <math.h>
^
Main.java:4: error: illegal character: '#'
#include <algorithm>
^
Main.java:5: error: illegal character: '#'
#include <vector>
^
Main.java:6: error: illegal character: '#'
#include <string.h>
^
Main.java:7: error: illegal character: '#'
#include <set>
^
Main.java:8: error: illegal character: '#'
#include <map>
^
Main.java:9: error: illegal character: '#'
#include <bitset>
^
Main.java:10: error: illegal character: '#'
#include <time.h>
^
Main.java:13: error: class, interface, or enum expected
typedef vector <int> vi;
^
Main.java:15: error: illegal character: '#'
#define ll long long
^
Main.java:15: error: class, interface, or enum expected
#define ll long long
        ^
Main.java:16: error: illegal character: '#'
#define pb push_back
^
Main.java:17: error: illegal character: '#'
#define ld double
^
Main.java:18: error: illegal character: '#'
#define pld pair <ld, ld>
^
Main.java:19: error: illegal character: '#'
#define pll pair <ll, ll>
^
Main.java:20: error: illegal character: '#'
#define fi first
^
Main.java:21: error: illegal character: '#'
#define pii pair <int, int>
^
Main.java:22: error: illegal character: '#'
#define se second
^
Main.java:23: error: illegal character: '#'
#define mp make_pair
^
Main.java:26: error: class, interface, or enum expected
const int INF = 1000 * 1000;
^
Main.java:28: error: class, interface, or enum expected
int cnt[MAXN], pr[MAXN], ind[MAXN], num[MAXN];
^
Main.java:29: error: class, interface, or enum expected
int cntt = 0;
^
Main.java:30: error: class, interface, or enum expected
vector <int> g[MAXN];
^
Main.java:31: error: class, interface, or enum expected
bool is_heavy(int v, int pr)
^
Main.java:34: error: class, interface, or enum expected
}
^
Main.java:38: error: illegal start of type
public:
      ^
Main.java:38: error: ';' expected
public:
       ^
Main.java:39: error: <identifier> expected
	int len;
	       ^
Main.java:98: error: class, interface, or enum expected
tree t[MAXN];
^
Main.java:99: error: class, interface, or enum expected
int dfs(int v, int _pr)
^
Main.java:102: error: class, interface, or enum expected
	cnt[v] = 1;
	^
Main.java:103: error: class, interface, or enum expected
	for (int i = 0; i < (int)g[v].size(); i++)
	^
Main.java:103: error: class, interface, or enum expected
	for (int i = 0; i < (int)g[v].size(); i++)
	                ^
Main.java:103: error: class, interface, or enum expected
	for (int i = 0; i < (int)g[v].size(); i++)
	                                      ^
Main.java:106: error: class, interface, or enum expected
	return cnt[v];
	^
Main.java:107: error: class, interface, or enum expected
}
^
Main.java:113: error: class, interface, or enum expected
	for (int i = 0; i < (int)g[v].size(); i++)
	^
Main.java:113: error: class, interface, or enum expected
	for (int i = 0; i < (int)g[v].size(); i++)
	                ^
Main.java:113: error: class, interface, or enum expected
	for (int i = 0; i < (int)g[v].size(); i++)
	                                      ^
Main.java:118: error: class, interface, or enum expected
			find_path(g[v][i]);
			^
Main.java:119: error: class, interface, or enum expected
		}
		^
Main.java:122: error: class, interface, or enum expected
}
^
Main.java:126: error: class, interface, or enum expected
int _type[MAXN * 4],  _v[MAXN * 4];
^
Main.java:127: error: class, interface, or enum expected
int main()
^
Main.java:134: error: class, interface, or enum expected
	int n, q;
	^
Main.java:135: error: class, interface, or enum expected
	cin >> n >> q;
	^
Main.java:136: error: class, interface, or enum expected
	for (int i = 0; i < n - 1; i++)
	^
Main.java:136: error: class, interface, or enum expected
	for (int i = 0; i < n - 1; i++)
	                ^
Main.java:136: error: class, interface, or enum expected
	for (int i = 0; i < n - 1; i++)
	                           ^
Main.java:139: error: class, interface, or enum expected
		cin >> a >> b;
		^
Main.java:140: error: class, interface, or enum expected
		a--, b--;
		^
Main.java:141: error: class, interface, or enum expected
		g[a].pb(b);
		^
Main.java:142: error: class, interface, or enum expected
		g[b].pb(a);
		^
Main.java:143: error: class, interface, or enum expected
	}
	^
Main.java:144: error: class, interface, or enum expected
	for (int i = 0; i < q; i++)
	                ^
Main.java:144: error: class, interface, or enum expected
	for (int i = 0; i < q; i++)
	                       ^
Main.java:146: error: class, interface, or enum expected
	dfs(0, 0);
	^
Main.java:147: error: class, interface, or enum expected
	find_path(0);
	^
Main.java:157: error: class, interface, or enum expected
	for (int i = 0; i < q; i++)
	^
Main.java:157: error: class, interface, or enum expected
	for (int i = 0; i < q; i++)
	                ^
Main.java:157: error: class, interface, or enum expected
	for (int i = 0; i < q; i++)
	                       ^
Main.java:160: error: class, interface, or enum expected
		int v = _v[i];
		^
Main.java:161: error: class, interface, or enum expected
		v--;
		^
Main.java:162: error: class, interface, or enum expected
		if (type)
		^
Main.java:165: error: class, interface, or enum expected
			int ans = INF;
			^
Main.java:166: error: class, interface, or enum expected
			while (v && ans == INF)
			^
Main.java:169: error: class, interface, or enum expected
				v = t[num[v]].ne;
				^
Main.java:170: error: class, interface, or enum expected
			}
			^
Main.java:172: error: class, interface, or enum expected
			if (ans == INF)
			^
Main.java:174: error: class, interface, or enum expected
			else
			^
Main.java:176: error: class, interface, or enum expected
			cout << '\n';
			^
Main.java:177: error: class, interface, or enum expected
		}
		^
Main.java:181: error: class, interface, or enum expected
			if (v)
			^
Main.java:184: error: class, interface, or enum expected
				t[num[v]].update(ind[v] + len, 1, len, len * 2 - 1);
				^
Main.java:185: error: class, interface, or enum expected
			}
			^
Main.java:190: error: class, interface, or enum expected
}
^
79 errors
stdout
copy 
Standard output is empty
https://ideone.com/1U5Ruy
language:
Java (HotSpot 12)
created:
9 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!