Advertisement
aayyk

Untitled

Sep 28th, 2022
678
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2.  
  3. #ifdef LOCAL
  4. #include "debug.h"
  5. #else
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #define debug(x...)
  10. #endif
  11.  
  12. using namespace std;
  13.  
  14. //#define int ll
  15.  
  16. typedef long long ll;
  17. typedef long double ld;
  18. typedef pair <int, int> pii;
  19. #define sz(x) int((x).size())
  20.  
  21. template <typename T>
  22. using ordered_set = __gnu_pbds::tree <T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
  23.  
  24. #ifdef ONLINE_JUDGE
  25. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  26. #else
  27. mt19937 rng(1000 - 7);
  28. #endif
  29.  
  30. const int N = 2e5 + 10;
  31. //const ll MOD = 998244353;
  32. const ll MOD = 1e9 + 7;
  33. const ld eps = 5e-8;
  34. const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
  35.  
  36. int n, ans[N], e[N], f[N], p[N], X[N], Flag[N], k[N];
  37. vector <int> g[N];
  38. deque <int> d;
  39.  
  40. signed main() {
  41. #ifdef LOCAL
  42.     freopen("input.txt", "r", stdin);
  43.     freopen("output.txt", "w", stdout);
  44. #endif
  45.     cout << fixed << setprecision(9);
  46.     ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  47.  
  48.     cin >> n;
  49.     for (int i = 1; i <= n; i++) {
  50.         int type;
  51.         cin >> type;
  52.  
  53.         if (type == 1) {
  54.             int v, x;
  55.             cin >> v >> x;
  56.  
  57.             g[v].push_back(i);
  58.             p[i] = v;
  59.             Flag[i] = false;
  60.             X[i] = x;
  61.         }
  62.         else {
  63.             int v;
  64.             cin >> v;
  65.  
  66.             g[v].push_back(i);
  67.             p[i] = v;
  68.             Flag[i] = true;
  69.         }
  70.     }
  71.  
  72.     vector <int> st;
  73.     for (int v : g[0]) {
  74.         st.push_back(v);
  75.         p[v] = -1;
  76.     }
  77.  
  78.     while (!st.empty()) {
  79.         int u = st.back();
  80.         st.pop_back();
  81.  
  82.         if (u == -1) continue;
  83.         debug(u);
  84.  
  85.         if (!k[u]) { // entering
  86.             if (Flag[u]) {
  87.                 ans[u] = f[u] = d.front();
  88.                 e[u] = 1;
  89.                 d.pop_front();
  90.             }
  91.             else {
  92.                 d.push_back(X[u]);
  93.             }
  94.             k[u] = 1;
  95.         }
  96.  
  97.         debug(d);
  98.  
  99.         if (g[u].empty()) { // leaving
  100.             st.push_back(p[u]);
  101.             if (Flag[u]) {
  102.                 d.push_front(f[u]);
  103.             }
  104.             else {
  105.                 d.pop_back();
  106.             }
  107.         }
  108.         else {
  109.             int v = g[u].back();
  110.             g[u].pop_back();
  111.             st.push_back(v);
  112.         }
  113.     }
  114.  
  115.     for (int i = 1; i <= n; i++) {
  116.         if (e[i]) {
  117.             cout << ans[i] << "\n";
  118.         }
  119.     }
  120.  
  121.     return 0;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement