Advertisement
tumaryui

Untitled

Sep 11th, 2020
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define endl "\n"
  3. #define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. using namespace std;
  5. const int N = 3e5 + 10;
  6.  
  7. pair<int, int> gmin(int a, int b) {
  8. return {min(a, b), max(a, b)};
  9. }
  10.  
  11. //graph itself
  12. int n, m, q, timer;
  13. vector<int> gr[N], g[N];
  14.  
  15. //vis
  16. vector<int> vis;
  17.  
  18. struct dsu {
  19. vector<int> par, siz;
  20. int get(int v) {
  21. if(par[v] == v) return v;
  22. return par[v] = get(par[v]);
  23. }
  24. void uni(int a, int b) {
  25. a = get(a);
  26. b = get(b);
  27. if(a != b) {
  28. if(siz[a] > siz[b]) {
  29. swap(a, b);
  30. }
  31. par[a] = b;
  32. siz[b] += siz[a];
  33. }
  34. }
  35. void resize(int n) {
  36. par.resize(n + 1);
  37. siz.resize(n + 1);
  38. for(int i = 1; i <= n; i++) {
  39. par[i] = i;
  40. siz[i] = 1;
  41. }
  42. }
  43. } comp, strong;
  44.  
  45. //find bridges
  46. vector<pair<int, int>> bridges;
  47. vector<int> fup(N), tin(N);
  48. int up[N][20], tout[N], art[N];
  49.  
  50. void bdfs(int v, int pr = -1) {
  51. fup[v] = tin[v] = timer++;
  52. vis[v] = 1;
  53. int cnt = 0;
  54. for(auto it: gr[v]) {
  55. if(it == pr) continue;
  56. if(!vis[it]) {
  57. bdfs(it, v);
  58. fup[v] = min(fup[it], fup[v]);
  59. cnt++;
  60. } else {
  61. fup[v] = min(fup[v], tin[it]);
  62. }
  63. comp.uni(v, it);
  64. if(fup[it] > tin[v]) {
  65. bridges.push_back(gmin(it, v));
  66. }
  67. if(fup[it] >= tin[v] && pr != -1) {
  68. art[v] = 1;
  69. }
  70. }
  71. if(cnt > 1 && pr == -1) {
  72. art[v] = 1;
  73. }
  74. tout[v] = timer;
  75. }
  76.  
  77. void sbfs(int v) {
  78. vis[v] = 1;
  79. for(auto it: gr[v]) {
  80. if(binary_search(bridges.begin(), bridges.end(), gmin(v, it)) || vis[it]) continue;
  81.  
  82. strong.uni(v, it);
  83. sbfs(it);
  84. }
  85. }
  86.  
  87.  
  88. void calc(int v, int pr) {
  89. vis[v] = 1;
  90. up[v][0] = pr;
  91. for(int i = 1; i < 20; i++) {
  92. up[v][i] = up[up[v][i - 1]][i - 1];
  93. }
  94. for(auto it: g[v]) {
  95. if(it == pr) continue;
  96. calc(it, v);
  97. }
  98. }
  99.  
  100. bool upper(int a, int b) {
  101. return tin[a] <= tin[b] && tout[a] >= tout[b];
  102. }
  103.  
  104. int lca(int a, int b) {
  105. if(upper(a, b)) return a;
  106. if(upper(b, a)) return b;
  107. for(int i = 19; i >= 0; i--) {
  108. if(!upper(up[a][i], b)) {
  109. a = up[a][i];
  110. }
  111. }
  112. return up[a][0];
  113. }
  114.  
  115. main() {
  116. boost;
  117. cin >> n >> m >> q;
  118. comp.resize(n);
  119. strong.resize(n);
  120. vis.resize(n + 1);
  121. while(m--) {
  122. int l, r;
  123. cin >> l >> r;
  124. gr[l].push_back(r);
  125. gr[r].push_back(l);
  126. }
  127.  
  128. for(int i = 1; i <= n; i++) {
  129. if(!vis[i]) {
  130. bdfs(i);
  131. }
  132. }
  133.  
  134. sort(bridges.begin(), bridges.end());
  135. fill(vis.begin(), vis.end(), 0);
  136. //split into comps
  137. for(int i = 1; i <= n; i++) {
  138. if(!vis[i]) {
  139. sbfs(i);
  140. }
  141. }
  142.  
  143. //build new tree
  144. for(auto it: bridges) {
  145. int l = it.first, r = it.second;
  146. l = strong.get(l);
  147. r = strong.get(r);
  148. g[l].push_back(r);
  149. g[r].push_back(l);
  150. }
  151. fill(vis.begin(), vis.end(), 0);
  152.  
  153.  
  154. //lca shit goes here ...
  155. timer = 0;
  156. for(int i = 1; i <= n; i++) {
  157. if(!vis[strong.get(i)]) {
  158. calc(strong.get(i), strong.get(i));
  159. }
  160. }
  161.  
  162. //end lca shit
  163. //go for queries
  164.  
  165. while(q--) {
  166. int a, b, c;
  167. cin >> a >> b >> c;
  168. int sa, sb, sc;
  169. if(a == b && b != c) {
  170. cout << "NO" << endl;
  171. continue;
  172. }
  173. sa = strong.get(a), sb = strong.get(b), sc = strong.get(c);
  174. if(comp.get(a) != comp.get(b) || comp.get(a) != comp.get(c) || comp.get(b) != comp.get(c)) {
  175. cout << "NO" << endl;
  176. continue;
  177. }
  178. // i just made sure that all a b c are in same comp
  179.  
  180. if(sa == sb && sb == sc) {
  181. cout << "YES" << endl;
  182. continue;
  183. }
  184. //all in one cycle -
  185. if(a == c || b == c) {
  186. cout << "YES" << endl;
  187. continue;
  188. }
  189. if(tin[a] > tin[b]) {
  190. swap(sa, sb);
  191. swap(a, b);
  192. }
  193. if(binary_search(bridges.begin(), bridges.end(), gmin(a, b))) {
  194. cout << "NO" << endl;
  195. continue;
  196. }
  197. //a and c in same strong
  198.  
  199. if(sa == sc) {
  200. if(art[a]) {
  201. //deep analysis
  202. } else {
  203. cout << "YES" << endl;
  204. }
  205. continue;
  206. }
  207. if(sb == sc) {
  208. if(art[b]) {
  209. cout << "NO" << endl;
  210. } else {
  211. cout << "YES" << endl;
  212. }
  213. continue;
  214. }
  215. //bad code here
  216. if(sb == sa) {
  217. if(art[b]) {
  218. cout << "NO" << endl;
  219. } else {
  220. cout << "YES" << endl;
  221. }
  222. continue;
  223. }
  224.  
  225.  
  226. //last part, is c on simple path in the tree
  227. //a = c -> b
  228. if(upper(sa, sb)) {
  229. if(upper(sc, sb) && upper(sa, sc)) {
  230. cout << "YES" << endl;
  231. } else {
  232. cout << "NO" << endl;
  233. }
  234. continue;
  235. }
  236. int mid = lca(sa, sb);
  237. if(upper(mid, c) && (upper(c, b) || upper(c, a))) {
  238. cout << "YES" << endl;
  239. continue;
  240. }
  241. cout << "NO" << endl;
  242. }
  243. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement