Advertisement
Vince14

/<> 13306

Oct 5th, 2023
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <unordered_map>
  13. #include <numeric>
  14. #include <iomanip>
  15. using namespace std;
  16. #define pii pair<int , int>
  17. #define ll long long
  18. #define FAST ios_base::sync_with_stdio(false); cin.tie(NULL)
  19. const long long dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
  20. const long long dl[2] = {1, -1};
  21. const long long MOD = 1000000007;
  22. const long long MAXN = 200005;
  23.  
  24. int N, Q, par[MAXN], p[MAXN], sz[MAXN];
  25. vector<pair<int, pii>> q;
  26. vector<string> ans;
  27.  
  28. int Find(int x){
  29.     if(x == p[x]) return x;
  30.     return p[x] = Find(p[x]);
  31. }
  32. void Union(int a, int b){
  33.     a = Find(a); b = Find(b);
  34.     if(a == b) return;
  35.     if(sz[a] > sz[b]) swap(a, b);
  36.     p[a] = b;
  37.     sz[b] += sz[a];
  38. }
  39. string Check(int a, int b){
  40.     if(Find(a) == Find(b)){
  41.         return "YES";
  42.     }
  43.     else{
  44.         return "NO";
  45.     }
  46. }
  47. void init(){
  48.     for(int i = 1; i <= N; i++){
  49.         p[i] = i;
  50.         sz[i] = 1;
  51.     }
  52. }
  53.  
  54. int main() {
  55.     FAST;
  56.     cin >> N >> Q;
  57.     for(int i = 2; i <= N; i++){
  58.         cin >> par[i];
  59.     }
  60.     init();
  61.     for(int x, y, z, i = 0; i < N + Q - 1; i++){
  62.         cin >> x;
  63.         if(x == 0){
  64.             cin >> y;
  65.             q.push_back({x, {y, -1}});
  66.         }
  67.         else{
  68.             cin >> y >> z;
  69.             q.push_back({x, {y, z}});
  70.         }
  71.     }
  72.     reverse(q.begin(), q.end());
  73.     for(auto x : q){
  74.         if(x.first == 0){
  75.             Union(x.second.first, par[x.second.first]);
  76.         }
  77.         else{
  78.             ans.push_back(Check(x.second.first, x.second.second));
  79.         }
  80.     }
  81.     reverse(ans.begin(), ans.end());
  82.     for(auto x : ans){
  83.         cout << x << "\n";
  84.     }
  85. }
  86.  
  87. /*
  88. 11 5
  89. 7
  90. 4
  91. 1
  92. 9
  93. 11
  94. 1
  95. 11
  96. 1
  97. 3
  98. 7
  99. 0 11
  100. 1 8 5
  101. 1 3 9
  102. 0 10
  103. 0 9
  104. 0 7
  105. 1 2 7
  106. 0 5
  107. 1 1 10
  108. 0 8
  109. 0 6
  110. 0 2
  111. 1 1 3
  112. 0 3
  113. 0 4
  114.  */
  115.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement