Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- #define int int64_t
- #define double long double
- #define optimization ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
- #define FILE 10
- #define F first
- #define S second
- #define pb push_back
- #define pf push_front
- #define mp make_pair
- #define For(n) for(int i = 1; i <= n; i++)
- #define FOR(i, n) for(i; i <= n; i++)
- #pragma GCC optimize("O3")
- #pragma GCC target("avx,avx2,fma")
- #pragma GCC optimization ("unroll-loops")
- using namespace std;
- using namespace __gnu_pbds;
- const int N = 1e5;
- const int MAX = LLONG_MAX;
- const int MIN = LLONG_MIN;
- const int MOD = 1e9 + 7;
- template<typename T>
- using orset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- template<typename T, typename K>
- using ormap = tree <T, K, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
- mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
- typedef pair <int, int> pii;
- int max_in_array(int n, deque <int> a)
- {
- int mx = MIN;
- for (int i = 0; i < n; i++)
- mx = max(mx, a [i]);
- return mx;
- }
- int min_in_array(int n, deque <int> a)
- {
- int mn = MAX;
- for (int i = 0; i < n; i++)
- mn = min(mn, a [i]);
- return mn;
- }
- int lcm(int x, int y)
- {
- return(x * y / __gcd(x, y));
- }
- int sqr(int x)
- {
- return x * x;
- }
- double log(double a, double b)
- {
- return log(b) / log(a);
- }
- int binpow(int x, int y)
- {
- if (y == 0)
- return 1;
- if (y & 1)
- return x * binpow(x, y - 1);
- else
- {
- int z = binpow(x, y / 2);
- return sqr(z);
- }
- }
- double binpow (double x, double y, bool d)
- {
- return exp(y * log(x));
- }
- class graph
- {
- public:
- int vertex, edge;
- deque <int> distance, parent;
- graph();
- deque <deque <int>> gr;
- private:
- deque <bool> visited, used;
- public:
- void init()
- {
- gr.resize(vertex + 1);
- parent.resize(vertex + 1);
- visited.resize(vertex + 1);
- used.resize(vertex + 1);
- distance.resize(vertex + 1);
- visited = {};
- distance = {};
- used = {};
- parent = {};
- parent [1] = 1;
- }
- deque <int> DFS(deque <int> u, bool ans)
- {
- if (!ans)
- {
- visited [u.front()] = 1;
- if (u.front() == 1)
- return {};
- DFS({parent [u.front()]}, 0);
- return {};
- }
- else
- {
- if (!visited [u.front()])
- {
- u.pf(parent [u.front()]);
- return DFS(u, 1);
- }
- else
- {
- if (u.size() == 1 && )
- return u;
- }
- }
- }
- void belongs(int u)
- {
- if (gr [u].empty())
- return;
- if (gr [u].size() == 1)
- {
- parent [gr [u] [0]] = parent [u];
- belongs(gr [u] [0]);
- return;
- }
- for (auto i: gr [u])
- {
- parent [i] = u;
- belongs(i);
- }
- }
- void count(int u, int dst)
- {
- distance [u] = dst;
- for (auto i: gr [u])
- count(i, dst + 1);
- }
- //tree
- int ver, root = 1;
- deque <pair <deque <int>, int>> tr;
- set <int> have;
- void init(int v)
- {
- ver = v;
- tr.resize(1);
- }
- void add(int u)
- {
- visited = {};
- have.insert(u);
- if (tr.size() == 1)
- tr.pb({{}, u});
- else
- {
- DFS({u}, 0);
- deque <int> a;
- a = DFS({tr [root].S}, 1);
- int frnt = a.front();
- a.pop_front();
- while (!a.empty())
- {
- tr [frnt].F.pb(a.front());
- a.pop_front();
- }
- }
- }
- void erase(int u)
- {
- visited = {};
- have.erase(u);
- int frnt = u;
- while (!have(frnt) && tr [frnt].F.size() == 1)
- {
- }
- }
- int rezult()
- {
- }
- };
- void solve()
- {
- graph v;
- cin >> v.vertex;
- v.init();
- For(v.vertex)
- {
- int k;
- cin >> k;
- int j = 1;
- FOR(j, k)
- {
- int u;
- cin >> u;
- v.gr [i].pb(u);
- v.parent [u] = i;
- }
- }
- v.count(1, 0);
- v.belongs(1);
- int q;
- cin >> q;
- v.init(v.vertex);
- while (q--)
- {
- int type, vert;
- cin >> type >> vert;
- if (type == 1)
- v.add(vert);
- else
- v.erase(vert);
- cout << v.rezult() << "\n";
- }
- }
- int32_t main()
- {
- optimization
- #ifdef FILE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- int t = 1;
- //cin >> t;
- while (t--)
- {
- solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment