fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using PII = pair<ll, ll>;
  5. #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
  6. #define REP(i, n) FOR(i, 0, n)
  7. #define ALL(x) x.begin(), x.end()
  8. template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
  9. template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
  10. struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
  11. #ifdef DEBUG_ 
  12. #include "../program_contest_library/memo/dump.hpp"
  13. #else
  14. #define dump(...)
  15. #endif
  16. const ll INF = 1LL<<60;
  17.  
  18. template<typename M>
  19. class LinkCutTree {
  20. public:
  21.     using T = typename M::T;
  22.     using E = typename M::E;
  23.  
  24.     struct node {
  25.         int sz, idx;
  26.         T val, sum;
  27.         E lazy;
  28.         node *left, *right, *par;
  29.         bool rev;
  30.         node(int idx) : sz(1), idx(idx), val(M::T0()), sum(M::T0()), lazy(M::E0()),
  31.             left(nullptr), right(nullptr), par(nullptr), rev(false) {}
  32.         node(T _val, int idx) : sz(1), idx(idx), val(_val), sum(_val), lazy(M::E0()),
  33.             left(nullptr), right(nullptr), par(nullptr), rev(false) {}
  34.         inline bool isRoot() const {
  35.             return (!par) || (par->left != this && par->right != this);
  36.         }
  37.         void push() {
  38.             if(lazy != M::E0()) {
  39.                 val = M::g(val, lazy, 1), sum = M::g(sum, lazy, sz);
  40.                 if(left) left->lazy = M::h(left->lazy, lazy);
  41.                 if(right) right->lazy = M::h(right->lazy, lazy);
  42.                 lazy = M::E0();
  43.             }
  44.             if(rev) {
  45.                 swap(left, right);
  46.                 sum = M::s(sum);
  47.                 if(left) left->rev ^= true;
  48.                 if(right) right->rev ^= true;
  49.                 rev = false;
  50.             }
  51.         }
  52.         void eval() {
  53.             sz = 1, sum = val;
  54.             if(left) left->push(), sz += left->sz, sum = M::f(left->sum, sum);
  55.             if(right) right->push(), sz += right->sz, sum = M::f(sum, right->sum);
  56.         }
  57.     };
  58.  
  59. private:
  60.     void rotate(node *u, bool right) {
  61.         node *p = u->par, *g = p->par;
  62.         if(right) {
  63.             if((p->left = u->right)) u->right->par = p;
  64.             u->right = p, p->par = u;
  65.         } else {
  66.             if((p->right = u->left)) u->left->par = p;
  67.             u->left = p, p->par = u;
  68.         }
  69.         p->eval(), u->eval(), u->par = g;
  70.         if(!g) return;
  71.         if(g->left == p) g->left = u;
  72.         if(g->right == p) g->right = u;
  73.         g->eval();
  74.     }
  75.     // uをsplay木の根にする
  76.     void splay(node *u) {
  77.         while(!u->isRoot()) {
  78.             node *p = u->par, *gp = p->par;
  79.             if(p->isRoot()) { // zig
  80.                 p->push(), u->push();
  81.                 rotate(u, (u == p->left));
  82.             } else {
  83.                 gp->push(), p->push(), u->push();
  84.                 bool flag = (u == p->left);
  85.                 if((u == p->left) == (p == gp->left)) { // zig-zig
  86.                     rotate(p, flag), rotate(u, flag);
  87.                 } else { // zig-zag
  88.                     rotate(u, flag), rotate(u, !flag);
  89.                 }
  90.             }
  91.         }
  92.         u->push();
  93.     }
  94.     // 頂点uから根へのパスをつなげる
  95.     node* expose(node *u) {
  96.         node *last = nullptr;
  97.         for(node *v = u; v; v = v->par) {
  98.             splay(v);
  99.             v->right = last;
  100.             v->eval();
  101.             last = v;
  102.         }
  103.         splay(u);
  104.         return last;
  105.     }
  106.     void evert(node *u) {
  107.         expose(u), u->rev = !(u->rev), u->push();
  108.     }
  109.     bool connected(node *u, node *v) {
  110.         expose(u), expose(v);
  111.         return u == v || u->par;
  112.     }
  113.     void link(node *u, node *v) {
  114.         evert(u), u->par = v;
  115.     }
  116.     void cut(node *u) { // uと親の辺を切る
  117.         expose(u), u->left->par = nullptr, u->left = nullptr, u->eval();
  118.     }
  119.     void cut(node *u, node *v) {
  120.         expose(u), expose(v);
  121.         if(u->isRoot()) u->par = nullptr;
  122.         else v->left->par = nullptr, v->left = nullptr, v->eval();
  123.     }
  124.     node* lca(node *u, node *v) {
  125.         expose(u);
  126.         return expose(v);
  127.     }
  128.     int depth(node *u) {
  129.         expose(u);
  130.         return u->sz - 1;
  131.     }
  132.     void toRoot_range(node *u, const E x) {
  133.         expose(u);
  134.         u->lazy = M::h(u->lazy, x), u->push();
  135.     }
  136.     void range(node *u, node *v, const E x) {
  137.         evert(u), expose(v);
  138.         v->lazy = M::h(v->lazy, x), v->push();
  139.     }
  140.     void toRoot_query(node *u) {
  141.         expose(u);
  142.         return u->sum;
  143.     }
  144.     T query(node *u, node *v) {
  145.         evert(u), expose(v);
  146.         return v->sum;
  147.     }
  148.     node* get_kth(node *u, node *v, int k) {
  149.         evert(v), expose(u);
  150.         while(u) {
  151.             push(u);
  152.             if(u->right && u->right->sz > k) u = u->right;
  153.             else {
  154.                 if(u->right) k -= u->right->sz;
  155.                 if(k == 0) return u;
  156.                 k--;
  157.                 u = u->left;
  158.             }
  159.         }
  160.         return nullptr;
  161.     }
  162.  
  163. public:
  164.     const int n;
  165.     node** arr;
  166.     LinkCutTree(const vector<T> &v) : n(v.size()) { 
  167.         arr = new node*[n];
  168.         REP(i, n) arr[i] = new node(v[i], i);
  169.     }
  170.     ~LinkCutTree(){
  171.         REP(i, n) delete arr[i];
  172.         delete[] arr;
  173.     }
  174.     bool connected(int id1, int id2) { return connected(arr[id1], arr[id2]); }
  175.     void link(int id1, int id2) { return link(arr[id1], arr[id2]); }
  176.     void cut(int id) { return cut(arr[id]); } // uと親の辺を切る
  177.     void cut(int id1, int id2) { return cut(arr[id1], arr[id2]); }
  178.     int lca(int id1, int id2) { return lca(arr[id1], arr[id2])->idx; }
  179.     void evert(int id) { return evert(arr[id]); }
  180.     int depth(int id) { return depth(arr[id]); }
  181.     void toRoot_range(int id, const E x) { return toRoot_range(arr[id], x); }
  182.     void range(int id1, int id2, const E x) { return range(arr[id1], arr[id2], x); }
  183.     T toRoot_query(int id) { return toRoot_query(arr[id]); }
  184.     T query(int id1, int id2) { return query(arr[id1], arr[id2]); }
  185.     int get_kth(int id1, int id2, int k) {
  186.         node *u = get_kth(arr[id1], arr[id2], k);
  187.         return !u ? -1 : u->idx;
  188.     }
  189. };
  190.  
  191. struct monoid {
  192.     using T = ll;
  193.     using E = ll;
  194.     static T T0() { return -INF; }
  195.     static constexpr E E0() { return -INF; }
  196.     static T f(const T &x, const T &y) { return max(x, y); }
  197.     static T g(const T &x, const E &y, int sz) { return y; }
  198.     static E h(const E &x, const E &y) { return y; }
  199.     static T s(const T &x) { return x; }
  200. };
  201.  
  202. void solve() {
  203.     ll n;
  204.     cin >> n;
  205.     vector<ll> a(n-1), b(n-1), c(n-1);
  206.     REP(i, n-1) {
  207.         cin >> a[i] >> b[i] >> c[i];
  208.         a[i]--, b[i]--;
  209.     }
  210.  
  211.     vector<ll> init(2*n-1);
  212.     REP(i, n-1) init[n+i] = c[i];
  213.     LinkCutTree<monoid> lct(init);
  214.     REP(i, n-1) lct.link(a[i], n+i), lct.link(n+i, b[i]);
  215.  
  216.     while(1) {
  217.         string s;
  218.         cin >> s;
  219.         if(s[0]=='D') break;
  220.         if(s[0]=='Q') {
  221.             ll u, v;
  222.             cin >> u >> v;
  223.             u--, v--;
  224.             cout << lct.query(u, v) << "\n";
  225.         } else {
  226.             ll u, v;
  227.             cin >> u >> v;
  228.             u--;
  229.             lct.range(n+u, n+u, v);
  230.         }
  231.     }
  232.     cout << flush;
  233. }
  234.  
  235. int main(void) {
  236.     ll t;
  237.     cin >> t;
  238.     while(t--) solve();
  239.  
  240.     return 0;
  241. }
Runtime error #stdin #stdout #stderr 0s 4276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/Lpb1xw
problem QTREE, based on SPOJ submission 25179617 (CPP), 2020-01-03 08:38:29
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!