fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <functional>
  6. #include <cassert>
  7.  
  8. std::vector<int> slow(int n, std::vector<std::pair<int, char>> input) {
  9.     std::vector<char> cost(1+n);
  10.     std::vector<int> answ(1+n);
  11.     std::vector<std::vector<int>> edges(1+n);
  12.     // Edges from input vector:
  13.     for (int u = 2; u <= n; ++u) {
  14.         int p = input[u].first; 
  15.         cost[u] = input[u].second;
  16.         edges[p].push_back(u);
  17.         edges[u].push_back(p);
  18.     }
  19.     // DFS function:
  20.     std::function<std::string(int,int)> visit = [&](int u, int p) {
  21.         std::string best; int r = u;
  22.         for (int v : edges[u]) {
  23.             if (v == p) continue;
  24.             auto temp = cost[v] + visit(v, u); // get string from child
  25.             if (temp.size() > best.size()) { // comparison this string with best string at this moment
  26.                 best = temp;
  27.                 r = v;
  28.             } else if (temp.size() == best.size()) {
  29.                 if (temp > best || (temp == best && answ[v] < answ[r])) {
  30.                     best = temp;
  31.                     r = v;
  32.                 }
  33.             }
  34.         }
  35.         answ[u] = (r == u) ? r : answ[r];
  36.         return best;
  37.     };
  38.     visit(1,0); // run dfs from root
  39.     // Return answer
  40.     for (int u = 1; u <= n; ++u) {
  41.         if (answ[u] == u) answ[u] = 0;
  42.     }
  43.     return answ;
  44. }
  45.  
  46. std::vector<std::pair<int, char>> input(int& n) {
  47.     scanf("%d", &n);
  48.     std::vector<std::pair<int, char>> answ(1+n);
  49.     for (int u = 2; u <= n; ++u) {
  50.         int p; char c;
  51.         scanf("%d %c", &p, &c);
  52.         answ[u] = std::make_pair(p,c);
  53.     }
  54.     return answ;
  55. }
  56.  
  57. int main() {
  58.     int n;
  59.     auto in = input(n);
  60.     auto answ = slow(n, in);
  61.     for (int u = 1; u <= n; ++u) {
  62.         printf("%d\n", answ[u]);
  63.     }
  64.     return 0;
  65. }
Success #stdin #stdout 0s 4480KB
comments (?)
stdin
copy 
5
1 b
1 b
3 c
3 a
stdout
copy 
4
0
4
0
0
https://ideone.com/R2k3cx
language:
C++14 (gcc 8.3)
created:
5 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!