Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define forsn(i, s, n) for(int i=s;i<int(n);i++)
  6. #define forn(i, n) forsn(i, 0, n)
  7. #define all(v) v.begin(), v.end()
  8. #define rall(v) v.rbegin(), v.rend()
  9. #define NACHO ios_base::sync_with_stdio(0);cin.tie(NULL);
  10.  
  11. typedef long long tint;
  12.  
  13. struct Trie{
  14.     map<char, Trie> arbol;
  15.     bool finPalabra = false;
  16. };
  17.  
  18. bool encontrado = 1;
  19. string s;
  20. int tamPalabra;
  21.  
  22. void insertar(Trie &t, int pos) {
  23.     if(pos < tamPalabra){
  24.         if(pos == tamPalabra-1) t.finPalabra = true;
  25.         insertar(t.arbol[s[pos]], pos+1);
  26.     }
  27. }
  28.  
  29. bool consistent = 1;
  30.  
  31. void recorrer(Trie &t, const string &palabra){
  32.     if(t.finPalabra && t.arbol.size() > 1){ consistent = 0;}
  33.     for(auto &i:t.arbol) {
  34.         recorrer(i.second, palabra+i.first);
  35.     }
  36. }
  37.  
  38. int main(){
  39.     NACHO;
  40.     int tc; cin >> tc;
  41.     while(tc--){
  42.         consistent = 1;
  43.         int n; cin >> n;
  44.         Trie t;
  45.         forn(i, n){
  46.             cin >> s;
  47.             tamPalabra = int(s.size())+1;
  48.             insertar(t, 0);
  49.         }
  50.         recorrer(t, "");
  51.         if(consistent) cout << "YES" << "\n";
  52.         else cout << "NO" << "\n";
  53.     }
  54. }
  55. //
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement