daily pastebin goal
65%
SHARE
TWEET

Untitled

a guest Jun 13th, 2018 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <random>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #include <unordered_set>
  6. #include <set>
  7. //#include "Treap.h"
  8. //#include "ImplicitTreap.cpp"
  9. //#include "RootedTree.h"
  10. //#include "Graph.h"
  11.  
  12. using namespace std;
  13.  
  14. //
  15. // Created by newuserkk on 5/29/18.
  16. //
  17. struct RootedTreeNode {
  18.     int id;
  19.     RootedTreeNode* parent;
  20.     int parent_cost = 0;
  21.     set<RootedTreeNode*> children;
  22.     int color;
  23.     int depth = 1;
  24.     vector<RootedTreeNode*> lca_dp;
  25.  
  26.     explicit RootedTreeNode(int id);
  27.  
  28.     void recalc();
  29. };
  30.  
  31. struct RootedTree {
  32.     RootedTreeNode *root;
  33.     vector<RootedTreeNode*> nodes;
  34.  
  35.     explicit RootedTree(RootedTreeNode *root = nullptr);
  36.  
  37.     void add(RootedTreeNode *node, RootedTreeNode *child, int cost);
  38.  
  39.     void connect(RootedTreeNode *node, RootedTreeNode *child, int cost);
  40.  
  41.     void lca_precalc();
  42.  
  43.     RootedTreeNode *lca(RootedTreeNode *v, RootedTreeNode *u);
  44.  
  45.     RootedTreeNode* get_node(int id);
  46.  
  47.     int get_min_on_path(RootedTreeNode *u, RootedTreeNode *v);
  48.  
  49.     int size();
  50.  
  51. };
  52.  
  53.  
  54. int randint(int min, int max) {
  55.     random_device r;
  56.     default_random_engine e1(r());
  57.     uniform_int_distribution<int64_t> uniform_dist(min, max);
  58.     return (int) uniform_dist(e1);
  59. }
  60.  
  61. //
  62. // Created by newuserkk on 5/29/18.
  63. //
  64.  
  65. RootedTreeNode::RootedTreeNode(int id) {
  66.     this->id = id;
  67.  
  68. //    this->children = std::move(children);
  69. //    this->parent = parent;
  70.  
  71.     recalc();
  72. }
  73.  
  74. void RootedTreeNode::recalc() {
  75.     if (!parent) {
  76.         this->depth = 1;
  77.     } else {
  78.         this->depth = parent->depth + 1;
  79.     }
  80. }
  81.  
  82. RootedTree::RootedTree(RootedTreeNode *root) {
  83.     this->root = root;
  84.     nodes.push_back(root);
  85. }
  86.  
  87. void RootedTree::add(RootedTreeNode *node, RootedTreeNode *child, int cost) {
  88.     nodes.push_back(child);
  89.     connect(node, child, cost);
  90.     node->recalc();
  91.     child->recalc();
  92. }
  93.  
  94. void RootedTree::connect(RootedTreeNode *node, RootedTreeNode *child, int cost) {
  95.     node->children.insert(child);
  96.     child->parent = node;
  97.     child->parent_cost = cost;
  98. }
  99.  
  100. RootedTreeNode *RootedTree::lca(RootedTreeNode *v, RootedTreeNode *u) {
  101.     auto n = (int) floor(log2(nodes.size()));
  102.     RootedTreeNode *first = v;
  103.     RootedTreeNode *second = u;
  104.     if (first->depth > second->depth) {
  105.         swap(first, second);
  106.     }
  107.  
  108.     // second depth > first depth
  109.     for (auto i = n; i >= 0; --i) {
  110.         if (second->depth - pow(2, i) >= first->depth) {
  111.             second = second->lca_dp[i];
  112.         }
  113.     }
  114.  
  115.     if (first == second) {
  116.         return first;
  117.     }
  118.  
  119.     for (auto i = n; i >= 0; --i) {
  120.         if (first->lca_dp[i] != second->lca_dp[i]) {
  121.             first = first->lca_dp[i];
  122.             second = second->lca_dp[i];
  123.         }
  124.     }
  125.  
  126.     return first->lca_dp[0];
  127. }
  128.  
  129. void RootedTree::lca_precalc() {
  130.     int n = (int)nodes.size();
  131.     int lg = (n != 1 ? (int)ceil(log2(n)) : 1);
  132.     for (auto &node : nodes) {
  133.         for (int i = 0; i < lg; ++i) {
  134.             node->lca_dp.push_back(nullptr);
  135.         }
  136.         node->lca_dp[0] = node->parent ? node->parent : node;
  137.     }
  138.     for (int i = 1; i < lg; ++i) {
  139.         for (auto &node : nodes) {
  140.             node->lca_dp[i] = node->lca_dp[i - 1]->lca_dp[i - 1];
  141.         }
  142.     }
  143. }
  144.  
  145. int RootedTree::get_min_on_path(RootedTreeNode *u, RootedTreeNode *v) {
  146.     if (u == v) {
  147.         return 0;
  148.     }
  149.  
  150.     RootedTreeNode* lca_node = lca(u, v);
  151.     int res = INT32_MAX;
  152.  
  153.     if (lca_node != u) {
  154.         res = u->parent_cost;
  155.         RootedTreeNode *u_parent = u->parent;
  156.         while (u_parent != lca_node) {
  157.             res = min(res, u_parent->parent_cost);
  158.             u_parent = u_parent->parent;
  159.         }
  160.     }
  161.  
  162.     if (lca_node != v) {
  163.         res = min(res, v->parent_cost);
  164.         RootedTreeNode *v_parent = (v != lca_node ? v->parent : v);
  165.         while (v_parent != lca_node) {
  166.             res = min(res, v_parent->parent_cost);
  167.             v_parent = v_parent->parent;
  168.         }
  169.     }
  170.     return res;
  171. }
  172.  
  173. RootedTreeNode *RootedTree::get_node(int id) {
  174.     return nodes[id];
  175. }
  176.  
  177. int RootedTree::size() {
  178.     return (int)nodes.size();
  179. }
  180.  
  181.  
  182. void mainA() {
  183.     int n;
  184.     cin >> n;
  185.  
  186.     auto tree = new RootedTree(new RootedTreeNode(0));
  187.  
  188.     int x;
  189.     for (int i = 0; i < n - 1; ++i) {
  190.         cin >> x;
  191.         tree->add(tree->get_node(x - 1), new RootedTreeNode(tree->size()), 0);
  192.     }
  193.  
  194.     tree->lca_precalc();
  195.     int m, u, v;
  196.     cin >> m;
  197.     for (int i = 0; i < m; ++i) {
  198.         cin >> u >> v;
  199.         RootedTreeNode* lca = tree->lca(tree->get_node(u - 1), tree->get_node(v - 1));
  200.         cout << lca->id + 1 << "\n";
  201.     }
  202. }
  203.  
  204. void mainB() {
  205.     int n;
  206.     cin >> n;
  207.  
  208.     auto tree = new RootedTree(new RootedTreeNode(0));
  209.  
  210.     int p, cost;
  211.     for (int i = 0; i < n - 1; ++i) {
  212.         cin >> p >> cost;
  213.         tree->add(tree->get_node(p - 1), new RootedTreeNode(tree->size()), cost);
  214.     }
  215.  
  216.     tree->lca_precalc();
  217.     int m, u, v;
  218.     cin >> m;
  219.     for (int i = 0; i < m; ++i) {
  220.         cin >> u >> v;
  221.         cout << tree->get_min_on_path(tree->get_node(u - 1),
  222.                                       tree->get_node(v - 1)) << "\n";
  223.     }
  224. }
  225.  
  226. //void mainH() {
  227. //    int n;
  228. //    cin >> n;
  229. //
  230. //    auto tree = new RootedTree(new RootedTreeNode(0));
  231. //
  232. //    for (int i = 1; i < n; ++i) {
  233. //        tree->nodes.push_back(new RootedTreeNode(i));
  234. //    }
  235. //
  236. //    int parent, color;
  237. //    for (int i = 0; i < n; ++i) {
  238. //        cin >> parent >> color;
  239. //        if (parent == 0) {
  240. //            tree->root = tree->get_node(i);
  241. //        } else {
  242. //            tree->connect(tree->get_node(parent - 1), tree->get_node(i));
  243. //        }
  244. //        tree->get_node(i)->set_color(color);
  245. //    }
  246. //
  247. //    tree->dfs(tree->root);
  248. //    for (auto node: tree->nodes) {
  249. //        cout << node->subtree_colors_count << " ";
  250. //    }
  251. //}
  252.  
  253. //void mainI() {
  254. //    int n, m;
  255. //    cin >> n >> m;
  256. //    auto graph = new Graph();
  257. //    for (int i = 0; i < n; ++i) {
  258. //        graph->add_node(new EulerNode(i));
  259. //    }
  260. //
  261. //    string op;
  262. //    int u, v;
  263. //    for (int j = 0; j < m; ++j) {
  264. //        cin >> op;
  265. //        if (op == "link") {
  266. //            cin >> u >> v;
  267. //            graph->nodes[u]->tree->link(graph->nodes[u], graph->nodes[v]);
  268. //        } else if (op == "cut") {
  269. //            cin >> u >> v;
  270. //            graph->nodes[u]->tree->cut(graph->nodes[u], graph->nodes[v]);
  271. //        } else {
  272. //            cin >> u;
  273. //            cout << graph->nodes[u]->tree->get_size() << "\n";
  274. //        }
  275. //    }
  276. //}
  277.  
  278. int main(int argc, char *argv[]) {
  279.     string arg = (argc > 1 ? argv[1] : "");
  280.     if (arg == "--readfile") {
  281.         freopen("test.in", "r", stdin);
  282.     } else {
  283. //        freopen("minonpath.in", "r", stdin);
  284. //        freopen("minonpath.out", "w", stdout);
  285.     }
  286.     ios_base::sync_with_stdio(false);
  287.     mainA();
  288. //    mainB();
  289. //    mainH();
  290. //    mainI();
  291.     return 0;
  292. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top