fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/oyX7GA
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!