Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //#pragma GCC optimize("Ofast,unroll-loops")
- #ifdef LOCAL
- #include "debug.h"
- #else
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define debug(x...)
- #endif
- using namespace std;
- //#define int ll
- typedef long long ll;
- typedef long double ld;
- typedef pair <int, int> pii;
- #define sz(x) int((x).size())
- template <typename T>
- 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>;
- #ifdef ONLINE_JUDGE
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- #else
- mt19937 rng(1000 - 7);
- #endif
- const int N = 2e5 + 10;
- //const ll MOD = 998244353;
- const ll MOD = 1e9 + 7;
- const ld eps = 5e-8;
- const pii dir[] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
- int n, ans[N], e[N], f[N], p[N], X[N], Flag[N], k[N];
- vector <int> g[N];
- deque <int> d;
- signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- cout << fixed << setprecision(9);
- ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
- cin >> n;
- for (int i = 1; i <= n; i++) {
- int type;
- cin >> type;
- if (type == 1) {
- int v, x;
- cin >> v >> x;
- g[v].push_back(i);
- p[i] = v;
- Flag[i] = false;
- X[i] = x;
- }
- else {
- int v;
- cin >> v;
- g[v].push_back(i);
- p[i] = v;
- Flag[i] = true;
- }
- }
- vector <int> st;
- for (int v : g[0]) {
- st.push_back(v);
- p[v] = -1;
- }
- while (!st.empty()) {
- int u = st.back();
- st.pop_back();
- if (u == -1) continue;
- debug(u);
- if (!k[u]) { // entering
- if (Flag[u]) {
- ans[u] = f[u] = d.front();
- e[u] = 1;
- d.pop_front();
- }
- else {
- d.push_back(X[u]);
- }
- k[u] = 1;
- }
- debug(d);
- if (g[u].empty()) { // leaving
- st.push_back(p[u]);
- if (Flag[u]) {
- d.push_front(f[u]);
- }
- else {
- d.pop_back();
- }
- }
- else {
- int v = g[u].back();
- g[u].pop_back();
- st.push_back(v);
- }
- }
- for (int i = 1; i <= n; i++) {
- if (e[i]) {
- cout << ans[i] << "\n";
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement