fork download
copy 
  1. #include <bits/stdc++.h>
  2. #ifndef ONLINE_JUDGE
  3. #include "debug.h"
  4. #else
  5. #define debug(...)
  6. #endif
  7. #define int long long
  8. #define oo LLONG_MAX >> 2
  9. #define all(x) x.begin(), x.end()
  10. #define allr(x) x.rbegin(), x.rend()
  11. #define pb push_back
  12. #define pep_Guardiola      \
  13.   ios::sync_with_stdio(0); \
  14.   cin.tie(0);              \
  15.   cout.tie(0);
  16. using namespace std;
  17. void io()
  18. {
  19. #ifndef ONLINE_JUDGE
  20.   freopen("input.txt", "r", stdin);
  21.   // freopen("output.txt", "w", stdout);
  22. #endif
  23. }
  24. int n;
  25. struct Trie
  26. {
  27.   struct Node
  28.   {
  29.     int freq;
  30.     string s = "";
  31.     map<string, int> id;
  32.     bool end = 0;
  33.     Node() = default;
  34.   };
  35.   vector<Node> trie;
  36.   Trie() : trie(1) {}
  37.   void insert(const vector<string> &s)
  38.   {
  39.     int node = 0;
  40.     int n = s.size();
  41.     for (int i = 0; i < n; i++)
  42.     {
  43.       string cVal = s[i];
  44.       if (!trie[node].id.count(cVal))
  45.       {
  46.         int cur = trie.size();
  47.         trie.emplace_back();
  48.         trie[node].id[cVal] = cur;
  49.         trie[cur].s = s[i];
  50.         trie[cur].id[trie[node].s] = node;
  51.       }
  52.       node = trie[node].id[cVal];
  53.       trie[node].freq++;
  54.     }
  55.     trie[node].end = 1;
  56.   }
  57.  
  58.   int find(int node, int pr)
  59.   {
  60.     for (auto [k, v] : trie[node].id)
  61.     {
  62.       // cout << trie[v].freq << endl;
  63.       if (trie[v].freq > n / 2 && v != pr)
  64.       {
  65.         return find(v, node);
  66.       }
  67.     }
  68.     return node;
  69.   }
  70.  
  71.   int help(int node, int pr, int len = 0)
  72.   {
  73.     cout << trie[node].s << ' ';
  74.     int ans = 0;
  75.     for (auto [k, v] : trie[node].id)
  76.     {
  77.       if (v != pr)
  78.       {
  79.         ans += help(v, node, len + 1);
  80.       }
  81.     }
  82.     cout << "Back\n";
  83.     return ans + (trie[node].end ? len : 0);
  84.   }
  85. };
  86.  
  87. signed main()
  88. {
  89.   pep_Guardiola
  90.   io();
  91.   cin >> n;
  92.   Trie tr;
  93.   for (int i = 0; i < n; i++)
  94.   {
  95.     string s;
  96.     cin >> s;
  97.     vector<string> a;
  98.     string cur = "";
  99.     for (auto x : s)
  100.     {
  101.       if (x == '/')
  102.       {
  103.         if (cur != "")
  104.           a.push_back(cur);
  105.         cur = "";
  106.       }
  107.       else
  108.         cur += x;
  109.     }
  110.     if (cur != "")
  111.       a.push_back(cur);
  112.     tr.insert(a);
  113.   }
  114.  
  115.   int best = tr.find(0, -1);
  116.   cout << tr.trie[best].s << ' ' << best << endl;
  117.   cout << tr.help(best, -1, 0) << endl;
  118. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 0
 Back
0
https://ideone.com/g7czv9
language:
C++ (gcc 8.3)
created:
11 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!