ProgMe

Untitled

May 12th, 2020
256
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.38 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define int int64_t
  6. #define double long double
  7. #define optimization ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  8. #define FILE 10
  9. #define F first
  10. #define S second
  11. #define pb push_back
  12. #define pf push_front
  13. #define mp make_pair
  14. #define For(n) for(int i = 1; i <= n; i++)
  15. #define FOR(i, n) for(i; i <= n; i++)
  16.  
  17. #pragma GCC optimize("O3")
  18. #pragma GCC target("avx,avx2,fma")
  19. #pragma GCC optimization ("unroll-loops")
  20.  
  21. using namespace std;
  22. using namespace __gnu_pbds;
  23.  
  24. const int N = 1e5;
  25. const int MAX = LLONG_MAX;
  26. const int MIN = LLONG_MIN;
  27. const int MOD = 1e9 + 7;
  28.  
  29. template<typename T>
  30. using orset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  31. template<typename T, typename K>
  32. using ormap = tree <T, K, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  33. mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
  34.  
  35. typedef pair <int, int> pii;
  36.  
  37. int max_in_array(int n, deque <int> a)
  38. {
  39. int mx = MIN;
  40. for (int i = 0; i < n; i++)
  41. mx = max(mx, a [i]);
  42. return mx;
  43. }
  44.  
  45. int min_in_array(int n, deque <int> a)
  46. {
  47. int mn = MAX;
  48. for (int i = 0; i < n; i++)
  49. mn = min(mn, a [i]);
  50. return mn;
  51. }
  52.  
  53. int lcm(int x, int y)
  54. {
  55. return(x * y / __gcd(x, y));
  56. }
  57.  
  58. int sqr(int x)
  59. {
  60. return x * x;
  61. }
  62.  
  63. double log(double a, double b)
  64. {
  65. return log(b) / log(a);
  66. }
  67.  
  68. int binpow(int x, int y)
  69. {
  70. if (y == 0)
  71. return 1;
  72. if (y & 1)
  73. return x * binpow(x, y - 1);
  74. else
  75. {
  76. int z = binpow(x, y / 2);
  77. return sqr(z);
  78. }
  79. }
  80.  
  81. double binpow (double x, double y, bool d)
  82. {
  83. return exp(y * log(x));
  84. }
  85.  
  86. class graph
  87. {
  88. public:
  89. int vertex, edge;
  90. deque <int> distance, parent;
  91. graph();
  92. deque <deque <int>> gr;
  93. private:
  94. deque <bool> visited, used;
  95. public:
  96. void init()
  97. {
  98. gr.resize(vertex + 1);
  99. parent.resize(vertex + 1);
  100. visited.resize(vertex + 1);
  101. used.resize(vertex + 1);
  102. distance.resize(vertex + 1);
  103. visited = {};
  104. distance = {};
  105. used = {};
  106. parent = {};
  107. parent [1] = 1;
  108. }
  109. deque <int> DFS(deque <int> u, bool ans)
  110. {
  111. if (!ans)
  112. {
  113. visited [u.front()] = 1;
  114. if (u.front() == 1)
  115. return {};
  116. DFS({parent [u.front()]}, 0);
  117. return {};
  118. }
  119. else
  120. {
  121. if (!visited [u.front()])
  122. {
  123. u.pf(parent [u.front()]);
  124. return DFS(u, 1);
  125. }
  126. else
  127. {
  128. if (u.size() == 1 && )
  129. return u;
  130. }
  131. }
  132. }
  133. void belongs(int u)
  134. {
  135. if (gr [u].empty())
  136. return;
  137. if (gr [u].size() == 1)
  138. {
  139. parent [gr [u] [0]] = parent [u];
  140. belongs(gr [u] [0]);
  141. return;
  142. }
  143. for (auto i: gr [u])
  144. {
  145. parent [i] = u;
  146. belongs(i);
  147. }
  148. }
  149. void count(int u, int dst)
  150. {
  151. distance [u] = dst;
  152. for (auto i: gr [u])
  153. count(i, dst + 1);
  154. }
  155. //tree
  156. int ver, root = 1;
  157. deque <pair <deque <int>, int>> tr;
  158. set <int> have;
  159. void init(int v)
  160. {
  161. ver = v;
  162. tr.resize(1);
  163. }
  164. void add(int u)
  165. {
  166. visited = {};
  167. have.insert(u);
  168. if (tr.size() == 1)
  169. tr.pb({{}, u});
  170. else
  171. {
  172. DFS({u}, 0);
  173. deque <int> a;
  174. a = DFS({tr [root].S}, 1);
  175. int frnt = a.front();
  176. a.pop_front();
  177. while (!a.empty())
  178. {
  179. tr [frnt].F.pb(a.front());
  180. a.pop_front();
  181. }
  182. }
  183. }
  184. void erase(int u)
  185. {
  186. visited = {};
  187. have.erase(u);
  188. int frnt = u;
  189. while (!have(frnt) && tr [frnt].F.size() == 1)
  190. {
  191.  
  192. }
  193. }
  194. int rezult()
  195. {
  196.  
  197. }
  198. };
  199.  
  200. void solve()
  201. {
  202. graph v;
  203. cin >> v.vertex;
  204. v.init();
  205. For(v.vertex)
  206. {
  207. int k;
  208. cin >> k;
  209. int j = 1;
  210. FOR(j, k)
  211. {
  212. int u;
  213. cin >> u;
  214. v.gr [i].pb(u);
  215. v.parent [u] = i;
  216. }
  217. }
  218. v.count(1, 0);
  219. v.belongs(1);
  220. int q;
  221. cin >> q;
  222. v.init(v.vertex);
  223. while (q--)
  224. {
  225. int type, vert;
  226. cin >> type >> vert;
  227. if (type == 1)
  228. v.add(vert);
  229. else
  230. v.erase(vert);
  231. cout << v.rezult() << "\n";
  232. }
  233. }
  234.  
  235. int32_t main()
  236. {
  237. optimization
  238. #ifdef FILE
  239. freopen("input.txt", "r", stdin);
  240. freopen("output.txt", "w", stdout);
  241. #endif
  242. int t = 1;
  243. //cin >> t;
  244. while (t--)
  245. {
  246. solve();
  247. }
  248. }
Advertisement
Add Comment
Please, Sign In to add comment