fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define fr(m) for(int i=0; i<m; i++)
  7. #define fro(m) for(int i=1; i<m; i++)
  8. #define frj(m) for(int j=0; j<m; j++)
  9. #define frr(n) for(int i=n; i>=0; i--)
  10. #define pb push_back
  11. #define pf push_front
  12. #define orr ||
  13. #define nl '\n'
  14. #define nll cout<<'\n'
  15. #define mod 1000000007
  16. #define inf (1LL<<62)
  17. #define inff (1<<30)
  18. #define yes cout<<"YES"<<nl
  19. #define no cout<<"NO"<<nl
  20. #define ff first
  21. #define ss second
  22. #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
  23.  
  24. int trie[300005][100], num, n;
  25. int endshere[300005];
  26. ll ans;
  27.  
  28. void init(){
  29.     memset(trie,0,sizeof(trie));
  30.     memset(endshere,0,sizeof(endshere));
  31.     num=1;
  32. }
  33.  
  34. void addElement(string s){
  35.     int node=1;
  36.     for(char c : s){
  37.         int ch=c-' ';
  38.         if(!trie[node][ch]) trie[node][ch]=++num;
  39.         node=trie[node][ch];
  40.     }
  41.     endshere[node]++;
  42. }
  43.  
  44. void traverse(int node, string s){
  45.     if(endshere[node]){
  46.         cout<<s<<" ";
  47.         double ans=endshere[node]*100;
  48.         ans/=n;
  49.         cout<<setprecision(4)<<fixed<<ans<<nl;
  50.     }
  51.     fr(91){
  52.         if(trie[node][i]){
  53.             string s2=s;
  54.             char ch=' '+i;
  55.             s2.pb(ch);
  56.             traverse(trie[node][i],s2);
  57.         }
  58.     }
  59. }
  60.  
  61. int main()
  62. {
  63.     fastio;
  64.     int t, cnt=1;
  65.     cin>>t;
  66.     while(t--){
  67.         init();
  68.         string s;
  69.         if(cnt) getline(cin,s), getline(cin,s);
  70.         n=0;
  71.         while(getline(cin,s)){
  72.             if(s=="") break;
  73.             n++;
  74.             addElement(s);
  75.         }
  76.         traverse(1,"");
  77.         cnt=0;
  78.         nll;
  79.     }
  80.     return 0;
  81. }
Success #stdin #stdout 0.02s 122100KB
comments (?)
stdin
copy 
1

Red Alder
Ash
Aspen
Basswood
Ash
Beech
Yellow Birch
Ash
Cherry
Cottonwood
Ash
Cypress
Red Elm
Gum
Hackberry
White Oak
Hickory
Pecan
Hard Maple
White Oak
Soft Maple
Red Oak
Red Oak
White Oak
Poplan
Sassafras
Sycamore
Black Walnut
Willow
stdout
copy 
Ash 13.7931
Aspen 3.4483
Basswood 3.4483
Beech 3.4483
Black Walnut 3.4483
Cherry 3.4483
Cottonwood 3.4483
Cypress 3.4483
Gum 3.4483
Hackberry 3.4483
Hard Maple 3.4483
Hickory 3.4483
Pecan 3.4483
Poplan 3.4483
Red Alder 3.4483
Red Elm 3.4483
Red Oak 6.8966
Sassafras 3.4483
Soft Maple 3.4483
Sycamore 3.4483
White Oak 10.3448
Willow 3.4483
Yellow Birch 3.4483
https://ideone.com/LppzvT
language:
C++14 (gcc 8.3)
created:
2 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!