fork download
  1. #pragma comment(linker, "/stack:200000000")
  2. //#pragma GCC optimize("Ofast")
  3. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  4. #pragma GCC optimize ("O3")
  5. #pragma GCC target ("sse4")
  6. #include <bits/stdc++.h>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8. #include <ext/pb_ds/assoc_container.hpp>
  9.  
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Tree;
  13.  
  14. #define sz(x) (int)(x).size()
  15. #define ll long long
  16. #define ld long double
  17. #define mp make_pair
  18. #define pb push_back
  19. #define eb emplace_back
  20. #define pii pair <int, int>
  21. #define vi vector<int>
  22. #define f first
  23. #define s second
  24. #define lb lower_bound
  25. #define ub upper_bound
  26. #define all(x) x.begin(), x.end()
  27. #define vpi vector<pair<int, int>>
  28.  
  29. #define f0r(i,a) for(int i=0;i<a;i++)
  30. #define f1r(i,a,b) for(int i=a;i<b;i++)
  31.  
  32. void fast_io(){
  33. ios_base::sync_with_stdio(0);
  34. cin.tie(NULL);
  35. cout.tie(NULL);
  36. }
  37. void io(string taskname){
  38. string fin = taskname + ".in";
  39. string fout = taskname + ".out";
  40. const char* FIN = fin.c_str();
  41. const char* FOUT = fout.c_str();
  42. freopen(FIN, "r", stdin);
  43. freopen(FOUT, "w", stdout);
  44. fast_io();
  45. }
  46. const int MAX = 1e5+5;
  47. template<class T, int SZ> struct MaxSegTree {
  48. T sum[2*SZ], mn[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
  49. void init() {
  50. memset (sum,0,sizeof sum);
  51. memset (mn,0,sizeof mn);
  52. memset (lazy,0,sizeof lazy);
  53. }
  54. void push(int ind, int L, int R) {
  55. sum[ind] += (R-L+1)*lazy[ind];
  56. mn[ind] += lazy[ind];
  57. if (L != R) lazy[2*ind] += lazy[ind], lazy[2*ind+1] += lazy[ind];
  58. lazy[ind] = 0;
  59. }
  60. void pull(int ind) {
  61. sum[ind] = sum[2*ind]+sum[2*ind+1];
  62. mn[ind] = max(mn[2*ind],mn[2*ind+1]);
  63. }
  64. void build() {
  65. for(int i = SZ-1; i>=0; i--){
  66. pull(i);
  67. }
  68. }
  69.  
  70. T qsum(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
  71. push(ind,L,R);
  72. if (lo > R || L > hi) return 0;
  73. if (lo <= L && R <= hi) return sum[ind];
  74.  
  75. int M = (L+R)/2;
  76. return qsum(lo,hi,2*ind,L,M) + qsum(lo,hi,2*ind+1,M+1,R);
  77. }
  78.  
  79. T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ-1) {
  80. push(ind,L,R);
  81. if (lo > R || L > hi) return 0;
  82. if (lo <= L && R <= hi) return mn[ind];
  83.  
  84. int M = (L+R)/2;
  85. return max(qmax(lo,hi,2*ind,L,M), qmax(lo,hi,2*ind+1,M+1,R));
  86. }
  87.  
  88. void upd(int lo, int hi, ll inc, int ind = 1, int L = 0, int R = SZ-1) {
  89. push(ind,L,R);
  90. if (hi < L || R < lo) return;
  91. if (lo <= L && R <= hi) {
  92. lazy[ind] = inc;
  93. push(ind,L,R);
  94. return;
  95. }
  96.  
  97. int M = (L+R)/2;
  98. upd(lo,hi,inc,2*ind,L,M); upd(lo,hi,inc,2*ind+1,M+1,R);
  99. pull(ind);
  100. }
  101. };
  102. template<int SZ> struct DSU{
  103. int par[SZ], sz[SZ];
  104. void init(){
  105. for(int i = 0; i<SZ; i++){
  106. par[i] = i;
  107. sz[i] = 1;
  108. }
  109. }
  110. int get(int x){
  111. if(par[x] != x){
  112. par[x] = get(par[x]);
  113. }
  114. return par[x];
  115. }
  116. bool unite(int x, int y){
  117. x = get(x);
  118. y = get(y);
  119. if(x == y){
  120. return false;
  121. }
  122. if(sz[x] < sz[y]){
  123. swap(x, y);
  124. }
  125. sz[x] += sz[y];
  126. par[y] = x;
  127. return true;
  128. }
  129. };
  130. unordered_map<int, int> seg; //turns original ordering into seg tree ordering
  131. unordered_map<int, int> comp; //finds component in dsu into the index in the forest
  132.  
  133. vector<pii> queries; //holds queries
  134. vector<vi> forest; //forest of nodes
  135. vector<pii> bounds;
  136.  
  137. DSU<MAX> d;
  138. MaxSegTree<int, (1<<17)> mst;
  139.  
  140. vi adj[MAX];
  141. int vis [MAX];
  142. int sub [MAX];
  143. int depth [MAX];
  144. int id [MAX];
  145. int isRoot[MAX];
  146.  
  147. void dfs(int src, int tree){
  148. sub[src] = tree;
  149. vis[src] = 1;
  150. for(int neigh: adj[src]){
  151. if(vis[neigh] == 0){
  152. if(tree == -1){
  153. depth[neigh] = depth[src] + 1;
  154. dfs(neigh, neigh);
  155. }
  156. else{
  157. depth[neigh] = depth[src] +1;
  158. dfs(neigh, tree);
  159. }
  160. }
  161. }
  162. }
  163. int main(){
  164. io("newbarn");
  165. int q;
  166. cin >> q;
  167. d.init();
  168. int cur = 0;//label of nodes
  169. f0r(i, q){
  170. char c;
  171. int p;
  172. cin >> c >> p;
  173. p--;
  174. if(c == 'B'){
  175. if(p != -2){
  176. d.unite(p, cur);
  177. adj[cur].eb(p);
  178. adj[p].eb(cur);
  179. }
  180. queries.eb(mp(0, cur));
  181. cur++;
  182. }
  183. else{
  184. queries.eb(mp(1, p));
  185. }
  186. }
  187. int n = cur; //number of nodes
  188. int c = 0;
  189. f0r(i, n){
  190. id[i] = -1;
  191. }
  192. forest.resize(n+5);
  193. f0r(i, n){
  194. if(id[d.get(i)] == -1){
  195. id[d.get(i)] = c;
  196. forest[c].eb(i);
  197. c++;
  198. }
  199. else{
  200. forest[id[d.get(i)]].eb(i);
  201. }
  202. }
  203. cur = 0;
  204. f0r(i, sz(forest)){
  205. int st = cur;
  206. if(sz(forest[i]) == 0){
  207. continue;
  208. }
  209. comp[d.get(forest[i][0])] = i;
  210. f0r(j, sz(forest[i])){
  211. seg[forest[i][j]] = cur;
  212. if(j == sz(forest[i]) - 1){
  213. bounds.eb(mp(st, cur));
  214. }
  215. cur++;
  216. }
  217.  
  218. }
  219. f0r(i, sz(forest)){
  220. if(sz(forest[i]) == 0){
  221. continue;
  222. }
  223. if(vis[forest[i][0]] == 1){
  224. continue;
  225. }
  226. dfs(forest[i][0], -1);
  227. isRoot[forest[i][0]] = 1;
  228. }
  229.  
  230. mst.init();
  231. f0r(i, sz(queries)){
  232. int type = queries[i].f;
  233. int p = queries[i].s;
  234. if(type == 0){
  235. if(p <0){
  236. continue;
  237. }
  238. int loc = sub[p];
  239. if(loc<0){
  240. continue;
  241. }
  242. int amount = mst.qmax(seg[loc], seg[loc]);
  243. if(amount<depth[p]){
  244. mst.upd(seg[loc], seg[loc], depth[p] - amount);
  245. }
  246. }
  247. else{
  248. int idx = comp[d.get(p)];
  249. int l = bounds[idx].f;
  250. int r = bounds[idx].s;
  251. if(isRoot[p] == 1){
  252. cout << mst.qmax(l, r) << endl;
  253. continue;
  254. }
  255. int loc = sub[p];
  256. int ans = 0;
  257. if(seg[loc] > l){
  258. ans = depth[p] + mst.qmax(l, seg[loc]-1);
  259. }
  260. if(seg[loc] <r){
  261. ans = max(ans, depth[p] + mst.qmax(seg[loc] + 1, r));
  262. }
  263. int chain = max(mst.qmax(seg[loc], seg[loc]) - depth[p], depth[p]);
  264. cout << max(ans, chain)<< endl;
  265. }
  266. }
  267. return 0;
  268. }
  269.  
Runtime error #stdin #stdout #stderr 0s 23408KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error