fork download
copy 
  1. #include <cmath>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <fstream>
  7. #include <iostream>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 12345
  12. #define MAX 1037471823
  13.  
  14. using namespace std;
  15.  
  16. int l[MS], r[MS], h[MS], ph[MS];
  17. int n, m, x, y;
  18. bool rev[MS];
  19. char q[10];
  20.  
  21. void Down(int x) { int k; k = l[x], l[x] = r[x], r[x] = k, rev[x]^=1, rev[l[x]]^=1, rev[r[x]]^=1; }
  22.  
  23. void Splay(int x)
  24. {
  25. 	if (!x) return; int o = h[x]; if (rev[x]) Down(x);
  26. 	while (o)
  27. 	{
  28. 		if (rev[o]) { Down(o); Down(x); } if (!h[o]) ph[x] = ph[o], ph[o] = 0;
  29. 		if (l[o] == x) { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o]; l[o] = r[x]; h[r[x]] = o; h[o] = x, r[x] = o; }
  30. 		else { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o]; r[o] = l[x]; h[l[x]] = o; h[o] = x, l[x] = o; }
  31. 		o = h[x];
  32. 	}
  33. }
  34.  
  35. void Acc(int x)
  36. {
  37. 	int o; Splay(x); ph[r[x]] = x, h[r[x]] = 0, r[x] = 0;
  38. 	while (ph[x]) { o = ph[x]; Splay(o); ph[r[o]] = o, h[r[o]] = 0, r[o] = x, h[x] = o, ph[x] = 0, x = o; }
  39. }
  40.  
  41. void Evert(int x) { Acc(x); Splay(x); rev[x]^=1; }
  42.  
  43. int FindR(int x) { Acc(x); Splay(x); int o = x; while (l[o]) o = l[o]; return o; }
  44.  
  45. void Link(int x, int y) { Evert(x); Evert(y); Splay(y); ph[y] = x;  }
  46.  
  47. void Cut(int x, int y) { Evert(x); Acc(y); Splay(y); h[x] = l[y] = 0; }
  48.  
  49. int main()
  50. {
  51. 	scanf("%d%d", &n, &m);
  52. 	rep(i, 1, m) 
  53. 	{
  54. 		scanf("%s%d%d", q, &x, &y);
  55. 		if (q[0] == 'D') Cut(x, y);
  56. 		else if (q[0] == 'C') Link(x, y);
  57. 		else { if (FindR(x) == FindR(y)) printf("Yes\n"); else printf("No\n"); }
  58. 	}
  59. 	return 0;
  60. }
Success #stdin #stdout 0s 3504KB
comments (?)
stdin
copy 
200	5
Query	123	127
Connect	123	127
Query	123	127
Destroy	127	123
Query	123	127
stdout
copy 
No
Yes
No
https://ideone.com/ufl4pH
BZOJ 2049
language:
C++ (gcc 8.3)
created:
10 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!