fork download
copy 
  1. #define _CRT_SECURE_NO_DEPRECATE
  2.  
  3. #include <bitset>
  4. #include <array>
  5. #include <cstdlib>
  6. #include <cctype>
  7. #include <cassert>
  8. #include <cstdio>
  9. #include <climits>
  10. #include <iostream>
  11. #include <vector>
  12. #include <set>
  13. #include <sstream>
  14. #include <string>
  15. #include <cstring>
  16. #include <cmath>
  17. #include <algorithm>
  18. #include <unordered_map>
  19. #include <unordered_set>
  20. #include <map>
  21. #include <stack>
  22. #include <deque>
  23. #include <tuple>
  24. #include <queue>
  25. #include <exception>
  26. #include <functional>
  27. #include <iomanip>
  28. #ifndef __GNUC__
  29. #include <intrin.h>
  30. #endif
  31. #ifndef ONLINE_JUDGE
  32. #include <conio.h>
  33. #endif
  34. typedef long long ll;
  35. using namespace std;
  36. vector<vector<int>> e;
  37. vector<int> p;
  38. vector<int> v;
  39. vector<int> color;
  40. bool sost[2 << 16];
  41. vector<vector<unordered_map<int, pair<int, int>>>> um1;
  42. vector<int> len;
  43. vector<int> lvl;
  44. int uk = 0;
  45. void dfsobh(int pos, int last, unordered_map<int, pair<int, int>>& uk, int val1, int all)
  46. {
  47. 	uk.insert({ pos,{val1,all} });
  48. 	for (size_t i = 0; i < e[pos].size(); i++)
  49. 	{
  50. 		int to = e[pos][i];
  51. 		if (to == last || color[to])
  52. 			continue;
  53. 		dfsobh(to, pos, uk, val1 + v[to], all + 1);
  54. 	}
  55. }
  56. bool cmp(int a, int b)
  57. {
  58. 	return len[a] > len[b];
  59. }
  60. int dfs(int pos, int last, int curlen)
  61. {
  62. 	int buf;
  63. 	for (size_t i = 0; i < e[pos].size(); i++)
  64. 	{
  65. 		int to = e[pos][i];
  66. 		if (to == last || color[to])
  67. 			continue;
  68. 		buf = len[to] = dfs(to, pos, curlen);
  69. 	}
  70. 	sort(e[pos].begin(), e[pos].end());
  71. 	if (buf >= curlen / 2)
  72. 	{
  73. 		color[pos] = 1;
  74. 		for (size_t i = 0; i < e[pos].size(); i++)
  75. 		{
  76. 			int to = e[pos][i];
  77. 			if (to == last || color[to])
  78. 				continue;
  79. 			um1[pos].push_back(unordered_map<int, pair<int, int>>());
  80. 			dfsobh(to, pos, um1[pos][um1[pos].size() - 1], 0, 0);
  81. 			p[to] = pos;
  82. 			lvl[to] = lvl[pos] + 1;
  83. 		}
  84. 		for (size_t i = 0; i < e[pos].size(); i++)
  85. 		{
  86. 			int to = e[pos][i];
  87. 			if (color[to])
  88. 				continue;
  89. 			if (to == last)
  90. 				dfs(to, pos, curlen - buf);
  91. 			else
  92. 				dfs(to, pos, len[to]);
  93. 		}
  94. 	}
  95. 	else return buf;
  96. }
  97. void zapr(int a, int b)
  98. {
  99. 	int sa = a, sb = b;
  100. 	if (lvl[a] > lvl[b])
  101. 		swap(a, b);
  102. 	while (lvl[a] < lvl[b])
  103. 		a = p[a];
  104. 	while (a != b)
  105. 		a = p[a], b = p[b];
  106. 	int ida = -1, idb = -1;
  107. 	if (sa == a || sb == a)
  108. 	{
  109. 		if (sb == a)
  110. 			swap(a, b);
  111. 		ida = um1[a].size();
  112. 	}
  113. 	if (ida == -1)
  114. 	{
  115. 		for (size_t i = 0; i < um1[a].size(); i++)
  116. 		{
  117. 			if (um1[a][i].find(ida) != um1[a][i].end())
  118. 			{
  119. 				ida = i;
  120. 				break;
  121. 			}
  122. 		}
  123. 	}
  124. 	for (size_t i = 0; i < um1[a].size(); i++)
  125. 	{
  126. 		if (um1[a][i].find(idb) != um1[a][i].end())
  127. 		{
  128. 			idb = i;
  129. 			break;
  130. 		}
  131. 	}
  132. 	v[a] = !v[a];
  133. 	if (ida == um1[a].size())
  134. 	{
  135.  
  136. 	}
  137. 	return 
  138.  
  139. }
  140. int main()
  141. {
  142. 	ios_base::sync_with_stdio(false);
  143. 	cin.tie(NULL); 	cout.tie(NULL);
  144. #ifndef ONLINE_JUDGE 
  145. 	freopen("input.txt", "r", stdin);
  146. 	freopen("output.txt", "w", stdout);
  147. #else 
  148. 	/*freopen("input.txt", "r", stdin);
  149. 	freopen("output.txt", "w", stdout);*/
  150. #endif // ONLINE_JUDGE
  151. 	int n;
  152. 	cin >> n;
  153. 	e.resize(n);	
  154. 	len.resize(n);
  155. 	lvl.resize(n);
  156. 	um1.resize(n);
  157. 	for (size_t i = 0; i < n; i++)
  158. 	{
  159. 		int a, b;
  160. 		cin >> a >> b;
  161. 		a--; b--;
  162. 		e[a].push_back(b);
  163. 		e[b].push_back(a);
  164. 	}
  165. 	color.resize(n);
  166. 	p.resize(n);
  167. 	dfs(0, -1, n);
  168. 	int q;
  169. 	cin >> q;
  170. 	for (size_t i = 0; i < q; i++)
  171. 	{
  172. 		int a, b;
  173. 		cin >> a >> b;
  174. 		zapr(a,b)
  175. 	}
  176. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:1: error: illegal character: '#'
#define _CRT_SECURE_NO_DEPRECATE
^
Main.java:3: error: illegal character: '#'
#include <bitset>
^
Main.java:4: error: illegal character: '#'
#include <array>
^
Main.java:5: error: illegal character: '#'
#include <cstdlib>
^
Main.java:6: error: illegal character: '#'
#include <cctype>
^
Main.java:7: error: illegal character: '#'
#include <cassert>
^
Main.java:8: error: illegal character: '#'
#include <cstdio>
^
Main.java:9: error: illegal character: '#'
#include <climits>
^
Main.java:10: error: illegal character: '#'
#include <iostream>
^
Main.java:11: error: illegal character: '#'
#include <vector>
^
Main.java:12: error: illegal character: '#'
#include <set>
^
Main.java:13: error: illegal character: '#'
#include <sstream>
^
Main.java:14: error: illegal character: '#'
#include <string>
^
Main.java:15: error: illegal character: '#'
#include <cstring>
^
Main.java:16: error: illegal character: '#'
#include <cmath>
^
Main.java:17: error: illegal character: '#'
#include <algorithm>
^
Main.java:18: error: illegal character: '#'
#include <unordered_map>
^
Main.java:19: error: illegal character: '#'
#include <unordered_set>
^
Main.java:20: error: illegal character: '#'
#include <map>
^
Main.java:21: error: illegal character: '#'
#include <stack>
^
Main.java:22: error: illegal character: '#'
#include <deque>
^
Main.java:23: error: illegal character: '#'
#include <tuple>
^
Main.java:24: error: illegal character: '#'
#include <queue>
^
Main.java:25: error: illegal character: '#'
#include <exception>
^
Main.java:26: error: illegal character: '#'
#include <functional>
^
Main.java:27: error: illegal character: '#'
#include <iomanip>
^
Main.java:28: error: illegal character: '#'
#ifndef __GNUC__
^
Main.java:29: error: illegal character: '#'
#include <intrin.h>
^
Main.java:30: error: illegal character: '#'
#endif
^
Main.java:31: error: illegal character: '#'
#ifndef ONLINE_JUDGE
^
Main.java:32: error: illegal character: '#'
#include <conio.h>
^
Main.java:33: error: illegal character: '#'
#endif
^
Main.java:35: error: class, interface, or enum expected
using namespace std;
^
Main.java:36: error: class, interface, or enum expected
vector<vector<int>> e;
^
Main.java:37: error: class, interface, or enum expected
vector<int> p;
^
Main.java:38: error: class, interface, or enum expected
vector<int> v;
^
Main.java:39: error: class, interface, or enum expected
vector<int> color;
^
Main.java:40: error: class, interface, or enum expected
bool sost[2 << 16];
^
Main.java:41: error: class, interface, or enum expected
vector<vector<unordered_map<int, pair<int, int>>>> um1;
^
Main.java:42: error: class, interface, or enum expected
vector<int> len;
^
Main.java:43: error: class, interface, or enum expected
vector<int> lvl;
^
Main.java:44: error: class, interface, or enum expected
int uk = 0;
^
Main.java:45: error: class, interface, or enum expected
void dfsobh(int pos, int last, unordered_map<int, pair<int, int>>& uk, int val1, int all)
^
Main.java:48: error: class, interface, or enum expected
	for (size_t i = 0; i < e[pos].size(); i++)
	^
Main.java:48: error: class, interface, or enum expected
	for (size_t i = 0; i < e[pos].size(); i++)
	                   ^
Main.java:48: error: class, interface, or enum expected
	for (size_t i = 0; i < e[pos].size(); i++)
	                                      ^
Main.java:51: error: class, interface, or enum expected
		if (to == last || color[to])
		^
Main.java:53: error: class, interface, or enum expected
		dfsobh(to, pos, uk, val1 + v[to], all + 1);
		^
Main.java:54: error: class, interface, or enum expected
	}
	^
Main.java:59: error: class, interface, or enum expected
}
^
Main.java:63: error: class, interface, or enum expected
	for (size_t i = 0; i < e[pos].size(); i++)
	^
Main.java:63: error: class, interface, or enum expected
	for (size_t i = 0; i < e[pos].size(); i++)
	                   ^
Main.java:63: error: class, interface, or enum expected
	for (size_t i = 0; i < e[pos].size(); i++)
	                                      ^
Main.java:66: error: class, interface, or enum expected
		if (to == last || color[to])
		^
Main.java:68: error: class, interface, or enum expected
		buf = len[to] = dfs(to, pos, curlen);
		^
Main.java:69: error: class, interface, or enum expected
	}
	^
Main.java:71: error: class, interface, or enum expected
	if (buf >= curlen / 2)
	^
Main.java:74: error: class, interface, or enum expected
		for (size_t i = 0; i < e[pos].size(); i++)
		^
Main.java:74: error: class, interface, or enum expected
		for (size_t i = 0; i < e[pos].size(); i++)
		                   ^
Main.java:74: error: class, interface, or enum expected
		for (size_t i = 0; i < e[pos].size(); i++)
		                                      ^
Main.java:77: error: class, interface, or enum expected
			if (to == last || color[to])
			^
Main.java:79: error: class, interface, or enum expected
			um1[pos].push_back(unordered_map<int, pair<int, int>>());
			^
Main.java:80: error: class, interface, or enum expected
			dfsobh(to, pos, um1[pos][um1[pos].size() - 1], 0, 0);
			^
Main.java:81: error: class, interface, or enum expected
			p[to] = pos;
			^
Main.java:82: error: class, interface, or enum expected
			lvl[to] = lvl[pos] + 1;
			^
Main.java:83: error: class, interface, or enum expected
		}
		^
Main.java:84: error: class, interface, or enum expected
		for (size_t i = 0; i < e[pos].size(); i++)
		                   ^
Main.java:84: error: class, interface, or enum expected
		for (size_t i = 0; i < e[pos].size(); i++)
		                                      ^
Main.java:87: error: class, interface, or enum expected
			if (color[to])
			^
Main.java:89: error: class, interface, or enum expected
			if (to == last)
			^
Main.java:91: error: class, interface, or enum expected
			else
			^
Main.java:93: error: class, interface, or enum expected
		}
		^
Main.java:96: error: class, interface, or enum expected
}
^
Main.java:100: error: class, interface, or enum expected
	if (lvl[a] > lvl[b])
	^
Main.java:102: error: class, interface, or enum expected
	while (lvl[a] < lvl[b])
	^
Main.java:104: error: class, interface, or enum expected
	while (a != b)
	^
Main.java:106: error: class, interface, or enum expected
	int ida = -1, idb = -1;
	^
Main.java:107: error: class, interface, or enum expected
	if (sa == a || sb == a)
	^
Main.java:111: error: class, interface, or enum expected
		ida = um1[a].size();
		^
Main.java:112: error: class, interface, or enum expected
	}
	^
Main.java:115: error: class, interface, or enum expected
		for (size_t i = 0; i < um1[a].size(); i++)
		                   ^
Main.java:115: error: class, interface, or enum expected
		for (size_t i = 0; i < um1[a].size(); i++)
		                                      ^
Main.java:120: error: class, interface, or enum expected
				break;
				^
Main.java:121: error: class, interface, or enum expected
			}
			^
Main.java:124: error: class, interface, or enum expected
	for (size_t i = 0; i < um1[a].size(); i++)
	                   ^
Main.java:124: error: class, interface, or enum expected
	for (size_t i = 0; i < um1[a].size(); i++)
	                                      ^
Main.java:129: error: class, interface, or enum expected
			break;
			^
Main.java:130: error: class, interface, or enum expected
		}
		^
Main.java:133: error: class, interface, or enum expected
	if (ida == um1[a].size())
	^
Main.java:143: error: class, interface, or enum expected
	cin.tie(NULL); 	cout.tie(NULL);
	^
Main.java:143: error: class, interface, or enum expected
	cin.tie(NULL); 	cout.tie(NULL);
	               	^
Main.java:144: error: illegal character: '#'
#ifndef ONLINE_JUDGE 
^
Main.java:144: error: class, interface, or enum expected
#ifndef ONLINE_JUDGE 
        ^
Main.java:146: error: class, interface, or enum expected
	freopen("output.txt", "w", stdout);
	^
Main.java:147: error: illegal character: '#'
#else 
^
Main.java:150: error: illegal character: '#'
#endif // ONLINE_JUDGE
^
Main.java:151: error: class, interface, or enum expected
	int n;
	^
Main.java:152: error: class, interface, or enum expected
	cin >> n;
	^
Main.java:153: error: class, interface, or enum expected
	e.resize(n);	
	^
Main.java:154: error: class, interface, or enum expected
	len.resize(n);
	^
100 errors
stdout
copy 
Standard output is empty
https://ideone.com/UXFvzK
language:
Java (HotSpot 12)
created:
5 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!