fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long int
  3.  
  4. using namespace std;
  5.  
  6. const ll MOD = 998244353 ;
  7. const int N = 1e3 + 5;
  8. //EAZY..PIZZIIEE
  9.  
  10. struct Trie{
  11.     int count;
  12.     Trie * child[676];
  13.     Trie(){
  14.         for(int i = 0; i < 676; ++i) child[i] = NULL;
  15.         this->count = 0;
  16.     }
  17. };
  18.  
  19. Trie * head = new Trie();
  20.  
  21. void insert(vector<int> &a){
  22.     Trie * curr = head;
  23.     for(auto & x: a){
  24.         if( !curr->child[x] )
  25.             curr->child[x] = new Trie();
  26.         curr = curr -> child[x];
  27.     }
  28.     curr->count++;
  29. }
  30.  
  31. ll dfs(Trie * cur, int lp = 0){
  32.     ll ans = 0;
  33.  
  34.     for(int i = 0; i < 656; ++i){
  35.         if( cur->child[i]) {
  36.             ans += dfs(cur->child[i], lp + 1);
  37.             cur->count += cur->child[i]->count; 
  38.         }
  39.     }
  40.  
  41.     while( cur->count >= 2){
  42.         cur->count -= 2;
  43.         ans += lp * lp;
  44.     }
  45.     return ans;
  46. }
  47.  
  48.  
  49. void solve(){
  50.     int n; cin >> n;
  51.     vector<string> s(n);
  52.     for(int i = 0; i < n; ++i){
  53.         cin >> s[i];
  54.     }
  55.     //vector<int> a(n);
  56.     for(int i = 0;i < n; ++i){
  57.         vector<int> a = vector<int>(s[i].size());
  58.         string t = s[i];
  59.         reverse(t.begin(), t.end());
  60.         for(int j = 0; j < s[i].size(); ++j){
  61.             a[j] = (s[i][j] - 'a')*26 + (t[j] - 'a');
  62.         }
  63.         //insert this string into trie
  64.         insert(a);
  65.     }
  66.     dfs(head);
  67. }
  68.  
  69. int main(){
  70.     int t; cin >> t;
  71.     while(t--)
  72.         solve();
  73. }
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
1
6
abcdefghijkl
chef
world
code
abcxyzhijkl
word
stdout
copy 
Standard output is empty
https://ideone.com/5oF4vY
language:
C++14 (gcc 8.3)
created:
5 years 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!