fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. #pragma warning(disable : 4996)
  5. using namespace std;
  6. int n, m, q, pcnt, V, a[100009], b[100009], c[100009], perm[50009], idx[50009]; long long bit[50009][785]; bool used[50009]; vector<int> g[50009], rg[50009], G[50009];
  7. void dfs1(int pos) {
  8. 	used[pos] = true;
  9. 	for (int i : g[pos]) {
  10. 		if (!used[i]) dfs1(i);
  11. 	}
  12. 	perm[pcnt++] = pos;
  13. }
  14. void dfs2(int pos) {
  15. 	idx[pos] = V; used[pos] = true;
  16. 	for (int i : rg[pos]) {
  17. 		if (!used[i]) dfs2(i);
  18. 	}
  19. }
  20. int main() {
  21. 	scanf("%d %d", &n, &m);
  22. 	for (int i = 0; i < m; i++) {
  23. 		scanf("%d %d", &a[0], &b[0]);
  24. 		g[--a[0]].push_back(--b[0]);
  25. 		rg[b[0]].push_back(a[0]);
  26. 	}
  27. 	scanf("%d", &q);
  28. 	for (int i = 0; i < q; i++) {
  29. 		scanf("%d %d %d", &a[i], &b[i], &c[i]); b[i]--;
  30. 		if (a[i] == 2) c[i]--;
  31. 		else {
  32. 			if (c[i] == 0) {
  33. 				rg[n].push_back(b[i]);
  34. 				g[b[i]].push_back(n++);
  35. 			}
  36. 			else {
  37. 				rg[b[i]].push_back(n);
  38. 				g[n++].push_back(b[i]);
  39. 			}
  40. 		}
  41. 	}
  42. 	for (int i = 0; i < n; i++) {
  43. 		if (!used[i]) dfs1(i);
  44. 	}
  45. 	fill(used, used + n, false);
  46. 	for (int i = n - 1; i >= 0; i--) {
  47. 		if (!used[perm[i]]) dfs2(perm[i]);
  48. 		V++;
  49. 	}
  50. 	for (int i = 0; i < n; i++) {
  51. 		for (int j : g[i]) {
  52. 			if (idx[i] != idx[j]) {
  53. 				G[idx[i]].push_back(idx[j]);
  54. 			}
  55. 		}
  56. 	}
  57. 	for (int i = V - 1; i >= 0; i--) {
  58. 		bit[i][i >> 6] |= 1LL << (i & 63);
  59. 		for (int j : G[i]) {
  60. 			for (int k = 0; k < 782; k++) {
  61. 				bit[i][k] |= bit[j][k];
  62. 			}
  63. 		}
  64. 	}
  65. 	for (int i = 0; i < q; i++) {
  66. 		if (a[i] == 2) printf(bit[idx[b[i]]][idx[c[i]] >> 6] & (1LL << (idx[c[i]] & 63)) ? "Yes\n" : "No\n");
  67. 	}
  68. 	return 0;
  69. }
Success #stdin #stdout 0s 327872KB
comments (?)
stdin
copy 
4 4
1 2
1 3
2 4
3 4
5
1 2 0
2 3 5
2 1 5
1 1 1
2 6 4
stdout
copy 
No
Yes
Yes
https://ideone.com/kwR1QR
language:
C++14 (gcc 8.3)
created:
7 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!