Advertisement
_rashed

UVA 1556

Jul 11th, 2022
46
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.88 KB | None | 0 0
  1. #define ll long long
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int OO = 1e9;
  6. const double EPS = 1e-9;
  7.  
  8. string out[501];
  9.  
  10. void conc(int d, char c, int oi) {
  11.     if(oi < out[d].length()) {
  12.         out[d][oi] = c;
  13.     }
  14.     else {
  15.         out[d] += c;
  16.     }
  17. }
  18.  
  19.  
  20. class Trie {
  21.     map<char,Trie*> mp;
  22.     bool flag;
  23.  
  24.     public:
  25.     Trie() {
  26.         flag = 0;
  27.     }
  28.  
  29.     ~Trie() {
  30.         for(pair<char,Trie*> p : mp) {
  31.             delete p.second;
  32.         }
  33.     }
  34.  
  35.     void add(string &s, int idx = 0) {
  36.         if(s.length() == idx) {
  37.             flag = 1;
  38.             return;
  39.         }
  40.         if(mp.find(s[idx]) == mp.end()) {
  41.             mp[s[idx]] = new Trie();
  42.         }
  43.         if(s[idx] == '\\') {
  44.             flag = 1;
  45.         }
  46.         mp[s[idx]]->add(s,idx+1);
  47.     }
  48.  
  49.  
  50.  
  51.     void printAll(int oi = 0, int d = 0) {
  52.         if(flag) {
  53.             cout << string(d, ' ') << out[d].substr(0,oi) << "\n";
  54.         }
  55.         if(mp['\\']) {
  56.             //cout << string(d, ' ') << out[d].substr(0,oi) << "\n";
  57.  
  58.             //cout << "moved1 to" << p.first << " out is " << out << "\n";
  59.             mp['\\']->printAll(0,d+1);
  60.         }
  61.         for(pair<char,Trie*> p : mp) {
  62.             if(p.first == '\\') {
  63.                 continue;
  64.             }
  65.             else {
  66.                 conc(d,p.first,oi);
  67.                 //cout << "moved2 to" << p.first << " out is " << out << "\n";
  68.                 p.second->printAll(oi+1,d);
  69.             }
  70.         }
  71.     }
  72.  
  73. };
  74.  
  75. int main()
  76. {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(NULL);
  79.     cout.tie(NULL);
  80.     //freopen("out.txt","w",stdout);
  81.     int n;
  82.     while(cin >> n) {
  83.         Trie dict;
  84.         for(int i = 0; i < n; i++) {
  85.             string s;
  86.             cin >> s;
  87.             dict.add(s);
  88.         }
  89.         dict.printAll();
  90.         cout << "\n";
  91.     }
  92.     return 0;
  93. }
  94.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement