Advertisement
Guest User

Untitled

a guest
Apr 4th, 2020
274
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long tint;
  6.  
  7. #define forsn(i, s, n) for(int i=s;i<int(n);i++)
  8. #define forn(i, n) forsn(i, 0, n)
  9. #define all(v) v.begin(),v.end()
  10. #define rall(v) v.rbegin(), v.rend()
  11. #define NACHO ios::sync_with_stdio(0); cin.tie(NULL);
  12.  
  13. const int INF = 1e6;
  14. const int MOD = 1e9+7;
  15.  
  16. int t[503][26];
  17. int fin[503];
  18.  
  19. int depth[503];
  20.  
  21. int maxi = 0;
  22. string best = "";
  23. string a="";
  24.  
  25. void dfs(int node=0, int d=0){
  26.     depth[node]+=fin[node];
  27.     forn(i, 26){
  28.         if(t[node][i] != -1){
  29.             a+=(char)('a'+i);
  30.             dfs(t[node][i], d+1);
  31.             depth[node]+=depth[t[node][i]];
  32.         }
  33.     }
  34.     if(d*d*depth[node] > maxi){
  35.         maxi = d*d*depth[node];
  36.         best = a;
  37.     }
  38.     a.pop_back();
  39. }
  40.  
  41. int main(){
  42.     //ifstream cin("equipo.in");
  43.     //ofstream cout("equipo.out");
  44.     int sz; cin >> sz;
  45.     int n; cin >> n;
  46.     forn(i, 501){
  47.         forn(j, 26){
  48.             t[i][j]= -1;
  49.         }
  50.     }
  51.     int m = 1;
  52.     forn(i, n){
  53.         string s;
  54.         cin >> s;
  55.         int u=0;
  56.         for(char d : s) {
  57.             if(t[u][d-'a'] == -1)
  58.                 t[u][d-'a']=m++;
  59.             u=t[u][d-'a'];
  60.         }
  61.         ++fin[u];
  62.     }
  63.     dfs();
  64.     cout << maxi << "\n";
  65.     cout << best << "\n";
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement