fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define MAXN 100013
  5. int N, Q;
  6.  
  7. struct node {
  8. 	node *c[2], *p;
  9. 	bool flip;
  10.  
  11. 	bool r() { return !p || (this != p->c[0] && this != p->c[1]); }
  12. 	int d() { return r() ? -1 : this == p->c[1]; }
  13.  
  14. 	void push() {
  15. 		if (flip) {
  16. 			swap(c[0], c[1]);
  17. 			if (c[0]) c[0]->flip ^= 1;
  18. 			if (c[1]) c[1]->flip ^= 1;
  19. 			flip ^= 1;
  20. 		}
  21. 	}
  22.  
  23. 	static void connect(node* pa, node* ch, int d) {
  24. 		if (d != -1) pa->c[d] = ch;
  25. 		if (ch) ch->p = pa;
  26. 	}
  27.  
  28. 	void rot() {
  29. 		assert(!r());
  30.  
  31. 		node* pa = p;
  32. 		int x = d();
  33.  
  34. 		connect(pa->p, this, pa->d());
  35. 		connect(pa, c[!x], x);
  36. 		connect(this, pa, !x);
  37. 	}
  38.  
  39. 	void splay() {
  40. 		while (!r() && !p->r()) {
  41. 			p->p->push();
  42. 			p->push();
  43. 			push();
  44. 			if (p->d() == d()) p->rot();
  45. 			else rot();
  46. 			rot();
  47. 		}
  48. 		if (!r()) {
  49. 			p->push();
  50. 			push();
  51. 			rot();
  52. 		}
  53. 		push();
  54. 	}
  55.  
  56. 	void expose() {
  57. 		node* pre = nullptr;
  58. 		for (node* v = this; v; v = v->p) {
  59. 			v->splay();
  60. 			v->c[1] = pre;
  61. 			pre = v;
  62. 		}
  63. 		splay();
  64. 	}
  65.  
  66. 	void make_root() {
  67. 		expose();
  68. 		flip ^= 1;
  69. 	}
  70.  
  71. } verts[MAXN];
  72.  
  73. int main() {
  74. 	ios_base::sync_with_stdio(false);
  75. 	cin.tie(0);
  76.  
  77. 	cin >> N >> Q;
  78.  
  79. 	while (Q--) {
  80. 		string s; cin >> s;
  81. 		int a, b;
  82. 		cin >> a >> b;
  83. 		--a, --b;
  84. 		if (s[0] == 'c') {
  85. 			if (a == b)
  86. 				cout << "YES\n";
  87. 			else {
  88. 				verts[a].expose();
  89. 				verts[b].expose();
  90. 				cout << (verts[a].p ? "YES" : "NO") << '\n';
  91. 			}
  92. 		}
  93. 		else if (s[0] == 'a') {
  94. 			verts[a].make_root();
  95. 			verts[a].p = &verts[b];
  96. 		}
  97. 		else {
  98. 			verts[a].make_root();
  99. 			verts[b].expose();
  100. 			verts[b].c[0] = nullptr;
  101. 			verts[a].p = nullptr;
  102. 		}
  103. 	}
  104.  
  105. 	cout.flush();
  106. 	return 0;
  107. }
  108.  
Success #stdin #stdout 0s 5496KB
comments (?)
stdin
copy 
5 11
conn 1 5
add 1 2
add 1 3
add 3 4
add 5 4
conn 1 5
rem 4 5
conn 1 5
rem 3 4
add 3 5
conn 1 5
stdout
copy 
NO
YES
NO
YES
https://ideone.com/0mi6mH
language:
C++14 (gcc 8.3)
created:
4 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!