fork download 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <functional>
  6. #include <cassert>
  7. #include <ctime>
  8. #include <cstdlib>
  9.  
  10. typedef unsigned long long ull;
  11.  
  12. const ull mod = (ull(1) << 61) - 1;
  13.  
  14. inline ull add(ull a, ull b) {
  15.     return (a += b) < mod ? a : a - mod;
  16. }
  17.  
  18. inline ull sub(ull a, ull b) {
  19.     return (a -= b) < mod ? a : a + mod;
  20. }
  21.  
  22. inline ull mul(ull a, ull b) {
  23.     ull l1 = (uint32_t)a, h1 = a >> 32, l2 = (uint32_t)b, h2 = b >> 32;
  24.     ull l = l1*l2, m = l1*h2 + l2*h1, h = h1*h2;
  25.     ull ret = (l & mod) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
  26.     ret = (ret & mod) + (ret >> 61);
  27.     ret = (ret & mod) + (ret >> 61);
  28.     return ret-1;
  29. }
  30.  
  31. std::vector<int> fast(int n, std::vector<std::pair<int,char>> input) {
  32.     const int NMAX = (int)5e5, PMAX = 20;
  33.     std::vector<int> answ(1+n), len(1+n);
  34.     std::vector<std::vector<int>> edges(1+n);
  35.     std::vector<char> cost(1+n); // cost from child to parent
  36.     static int parent[PMAX][1+NMAX];
  37.     static ull hashes[PMAX][1+NMAX];
  38.     // Input:
  39.     for (int u = 2; u <= n; ++u) {
  40.         int p = input[u].first; 
  41.         cost[u] = input[u].second;
  42.         edges[p].push_back(u);
  43.         edges[u].push_back(p);
  44.         parent[0][u] = p;
  45.         hashes[0][u] = cost[u];
  46.     }
  47.     // Precalc powers of base:
  48.     const ull BASE = (int)1e9+7;
  49.     std::vector<ull> pow{1};
  50.     while ((int)pow.size() < NMAX) {
  51.         pow.push_back(mul(pow.back(), BASE));
  52.     }
  53.     // Precalc parents and hashes:
  54.     for (int p = 1; p < PMAX; ++p) {
  55.         for (int u = 1; u <= n; ++u) {
  56.             int v = parent[p-1][u];
  57.             if (v == 0) continue;
  58.             parent[p][u] = parent[p-1][v];
  59.             hashes[p][u] = add(mul(hashes[p-1][v], pow[1<<(p-1)]), hashes[p-1][u]);
  60.         }
  61.     }
  62.     // Get parent of vertex u with `nSteps` steps up:
  63.     std::function<int(int,int)> get_parent = [&](int u, int nSteps) {
  64.         for (int p = PMAX-1; p >= 0; --p) {
  65.             if (((nSteps >> p) & 1) == 1) {
  66.                 u = parent[p][u];
  67.             }
  68.         }
  69.         return u;
  70.     };
  71.     // Get hash from vertex u with `nSteps` steps up:
  72.     std::function<ull(int,int)> get_hash = [&](int u, int nSteps) {
  73.         int sum = 0; ull hash = 0;
  74.         for (int p = PMAX-1; p >= 0; --p) {
  75.             if (((nSteps >> p) & 1) == 1) {
  76.                 hash = add(hash, mul(hashes[p][u], pow[sum]));
  77.                 sum += (1 << p);
  78.                 u = parent[p][u];
  79.             }
  80.         }
  81.         return hash;
  82.     };
  83.     // DFS:
  84.     std::function<void(int,int)> visit = [&](int u, int p) {
  85.         int max = -1, r = u;
  86.         for (int v : edges[u]) {
  87.             if (p == v) continue;
  88.             visit(v,u);
  89.             if (len[v] > max) {
  90.                 max = len[v];
  91.                 r = v;
  92.             } else if (len[v] == max) {
  93.                 // find first not equal symbol
  94.                 int low = 0, high = max+2;
  95.                 while (high - low > 1) {
  96.                     int mid = (low + high) / 2;
  97.                     ull hash1 = get_hash(get_parent(answ[v], max+1-mid), mid);
  98.                     ull hash2 = get_hash(get_parent(answ[r], max+1-mid), mid);
  99.                     if (hash1 == hash2) {
  100.                         low = mid;
  101.                     } else {
  102.                         high = mid;
  103.                     }
  104.                 }
  105.                 if (low < max+1) {
  106.                     int pv = get_parent(answ[v], max-low);
  107.                     int pr = get_parent(answ[r], max-low);
  108.                     assert(cost[pv] != cost[pr]);
  109.                     if (cost[pv] > cost[pr]) {
  110.                         r = v;
  111.                     }
  112.                 } else if (answ[v] < answ[r]) {
  113.                     r = v;
  114.                 }
  115.             }
  116.         }
  117.         len[u] = max+1;
  118.         answ[u] = (r == u) ? r : answ[r]; 
  119.     };
  120.     visit(1,0); // Run dfs
  121.     // Return answer:
  122.     for (int u = 1; u <= n; ++u) {
  123.         answ[u] = (answ[u] == u) ? 0 : answ[u];
  124.     }
  125.     return answ;
  126. }
  127.  
  128. std::vector<int> slow(int n, std::vector<std::pair<int, char>> input) {
  129.     std::vector<char> cost(1+n);
  130.     std::vector<int> answ(1+n);
  131.     std::vector<std::vector<int>> edges(1+n);
  132.     // Input:
  133.     for (int u = 2; u <= n; ++u) {
  134.         int p = input[u].first; 
  135.         cost[u] = input[u].second;
  136.         edges[p].push_back(u);
  137.         edges[u].push_back(p);
  138.     }
  139.     std::function<std::string(int,int)> visit = [&](int u, int p) {
  140.         std::string best; int r = u;
  141.         for (int v : edges[u]) {
  142.             if (v == p) continue;
  143.             auto temp = cost[v] + visit(v, u);
  144.             if (temp.size() > best.size()) {
  145.                 best = temp;
  146.                 r = v;
  147.             } else if (temp.size() == best.size()) {
  148.                 if (temp > best || (temp == best && answ[v] < answ[r])) {
  149.                     best = temp;
  150.                     r = v;
  151.                 }
  152.             }
  153.         }
  154.         answ[u] = (r == u) ? r : answ[r];
  155.         return best;
  156.     };
  157.     visit(1,0);
  158.     for (int u = 1; u <= n; ++u) {
  159.         if (answ[u] == u) answ[u] = 0;
  160.     }
  161.     return answ;
  162. }
  163.  
  164. std::vector<std::pair<int, char>> input(int& n) {
  165.     scanf("%d", &n);
  166.     std::vector<std::pair<int, char>> answ(1+n);
  167.     for (int u = 2; u <= n; ++u) {
  168.         int p; char c;
  169.         scanf("%d %c", &p, &c);
  170.         answ[u] = std::make_pair(p,c);
  171.     }
  172.     return answ;
  173. }
  174.  
  175. int main() {
  176.     int n;
  177.     auto in = input(n);
  178.     auto answ1 = fast(n, in);
  179.     for (int u = 1; u <= n; ++u) {
  180.         printf("%d\n", answ1[u]);
  181.     }
  182.     return 0;
  183. }
Success #stdin #stdout 0.01s 6840KB
comments (?)
stdin 
5
1 b
1 b
3 c
3 a
stdout 
4
0
4
0
0
https://ideone.com/1How9A
language:
C++14 (gcc 8.3)
created:
6 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!