fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int NMAX=1e5;
  4. struct lct {
  5.     struct node {
  6.         int child[2];
  7.         int sum, rev_tag, parent, value;
  8.     };
  9.     node tree[NMAX+5];
  10.     void push(int node) {
  11.         if (tree[node].rev_tag==0) return;
  12.         swap(tree[node].child[0], tree[node].child[1]);
  13.         if (tree[node].child[0]) tree[tree[node].child[0]].rev_tag^=1;
  14.         if (tree[node].child[1]) tree[tree[node].child[1]].rev_tag^=1;
  15.         tree[node].rev_tag=0;
  16.     }
  17.     void pull(int node) {
  18.         tree[node].sum=tree[node].value;
  19.         if (tree[node].child[0]) tree[node].sum+=tree[tree[node].child[0]].sum;
  20.         if (tree[node].child[1]) tree[node].sum+=tree[tree[node].child[1]].sum;
  21.     }
  22.     int get(int node) {
  23.         if (!tree[node].parent) return -1;
  24.         if (node==tree[tree[node].parent].child[0]) return 0;
  25.         if (node==tree[tree[node].parent].child[1]) return 1;
  26.         return -1;
  27.     }
  28.     void rotate(int node) {
  29.         int p = tree[node].parent;
  30.         int pp = tree[p].parent;
  31.         int side1 = get(node);
  32.         int side2 = get(p);
  33.         tree[p].child[side1] = tree[node].child[side1 ^ 1];
  34.         if (tree[p].child[side1]) {
  35.             tree[tree[p].child[side1]].parent = p;
  36.         }
  37.         tree[node].child[side1 ^ 1] = p;
  38.         tree[p].parent = node;
  39.         tree[node].parent = pp;
  40.         if (side2 != -1) tree[pp].child[side2] = node;
  41.         pull(p);
  42.         pull(node);
  43.     }
  44.     void propagate(int node) {
  45.         if (get(node)!=-1) propagate(tree[node].parent);
  46.         push(node);
  47.     }
  48.     void splay(int node) {
  49.         propagate(node);
  50.         while (get(node)!=-1) {
  51.             int side1=get(node);
  52.             int side2=get(tree[node].parent);
  53.             if (side2!=-1) {
  54.                 if (side1==side2) {
  55.                     rotate(tree[node].parent);
  56.                 }else {
  57.                     rotate(node);
  58.                 }
  59.             }
  60.             rotate(node);
  61.         }
  62.     }
  63.     int access(int node) {
  64.         int last=0;
  65.         for (int cur=node;cur;last=cur, cur=tree[cur].parent) {
  66.             splay(cur);
  67.             tree[cur].child[1]=last;
  68.             pull(cur);
  69.         }
  70.         splay(node);
  71.         return last;
  72.     }
  73.     void make_root(int node) {
  74.         access(node);
  75.         tree[node].rev_tag^=1;
  76.     }
  77.     int find_root(int node) {
  78.         access(node);
  79.         while (tree[node].child[0]) {
  80.             push(node);
  81.             node=tree[node].child[0];
  82.         }
  83.         splay(node);
  84.         return node;
  85.     }
  86.     void link_unrooted(int u, int v) {
  87.         if (find_root(u)==find_root(v)) return;
  88.         make_root(u);
  89.         tree[u].parent=v;
  90.     }
  91.     void link_rooted(int u, int v) {
  92.         access(u);
  93.         tree[u].parent = v;
  94.     }
  95.     void cut_unrooted(int u, int v) {
  96.         if (find_root(u)!=find_root(v)) return;
  97.         make_root(u);
  98.         access(v);
  99.         if (tree[v].child[0]==u) {
  100.             tree[v].child[0]=0;
  101.             tree[u].parent=0;
  102.             pull(v);
  103.         }
  104.     }
  105.     void cut_rooted(int u, int v) {
  106.         access(u);
  107.         if (tree[u].child[0]) {
  108.             tree[tree[u].child[0]].parent = 0;
  109.             tree[u].child[0] = 0;
  110.             pull(u);
  111.         }
  112.     }
  113.     int lca(int u, int v) {
  114.         access(u);
  115.         return access(v);
  116.     }
  117. };
  118. lct tree;
  119. int main() {
  120.     int n, m;
  121.     cin>>n>>m;
  122.     for (int i=1;i<=m;i++) {
  123.         string s;
  124.         cin>>s;
  125.         if (s=="lca") {
  126.             int a, b;
  127.             cin>>a>>b;
  128.             cout<<tree.lca(a, b)<<'\n';
  129.         }else if (s=="link") {
  130.             int a, b;
  131.             cin>>a>>b;
  132.             tree.link_rooted(a,b);
  133.         }else {
  134.             int a;
  135.             cin>>a;
  136.             tree.access(a);
  137.             int p=tree.tree[a].child[0];
  138.             if (p) {
  139.                 tree.push(p);
  140.                 while (tree.tree[p].child[1]) {
  141.                     p=tree.tree[p].child[1];
  142.                     tree.push(p);
  143.                 }
  144.                 tree.cut_rooted(a, p);
  145.             }
  146.         }
  147.     }
  148. }
  149.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6GAFZp
problem DYNALCA, based on SPOJ submission 35771549 (CPP14), 2026-05-23 13:16:54
language:
C++14 (gcc 8.3)
created:
9 hours 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!