oj.uz

Submission #50303

# Submission time Handle Problem Language Result Execution time Memory
50303 2018-06-09T18:17:00 Z computerbox Lozinke (COCI17_lozinke) C++14
100 / 100
 730 ms 95012 KB 
 //ID:computerbox --> Hajiyev Huseyn
#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define _CRT_SECURE_NO_WARNINGS
//#include <boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;
#define FAST_READ ios_base::sync_with_stdio(0);/*cin.tie(0); cout.tie(0);*/
#define in freopen("input.txt", "r", stdin);
#define out freopen("output.txt", "w", stdout);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define COUT(n, a) cout<< fixed << setprecision(a) << n<<endl
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";
#define CURTIME() cerr << clock() * 1.0 / CLOCKS_PER_SEC << endl
#define DTIME(ccc) __begin = clock(); ccc; cerr<<"Time of work = "<<(clock()-__begin)/CLOCKS_PER_SEC<<endl;
#define MAXN 500010

using namespace std;

set<ll>leaf[500010];
ll trie[27][MAXN];
ll sz;
void add_string(string stroka,ll index)
{
   ll v=0;
   for(ll i=0;i<stroka.size();i++)
   {
     if(trie[stroka[i]-'a'][v]==0)
     {
       trie[stroka[i]-'a'][v]=sz++;
     }
     v=trie[stroka[i]-'a'][v];
     leaf[v].insert(index);
   }
}

ll find(string stroka)
{
  ll v=0;
  ll ans=0;
  for(ll i=0;i<stroka.size();i++)
  {
    v=trie[stroka[i]-'a'][v];
  }
  ans=leaf[v].size();
  return ans-1;
}

ll n;
vector<string>nuj;
string stroka;
string abc;
int main(){
FAST_READ;
cin.tie(0);
cin>>n;

sz=1;
for(ll i=1;i<=n;i++)
{
  cin>>stroka;
  string neww="";
  for(ll j=0;j<(ll)stroka.size();j++)
  {
    neww="";
     for(ll jj=j;jj<(ll)stroka.size();jj++)
     {
      neww+=stroka[jj];
      //debt(neww,j);
      add_string(neww,i);
     }
  }

  nuj.pb(stroka);
}

ll cnt=0;
for(ll i=0;i<nuj.size();i++)
{
  ll ans=find(nuj[i]);
  //deb(ans);
  cnt=cnt+ans;
}
cout<<cnt<<endl;



return 0;
}

Compilation message

lozinke.cpp: In function 'void add_string(std::__cxx11::string, long long int)':
lozinke.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(ll i=0;i<stroka.size();i++)
               ~^~~~~~~~~~~~~~
lozinke.cpp: In function 'long long int find(std::__cxx11::string)':
lozinke.cpp:48:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i=0;i<stroka.size();i++)
              ~^~~~~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:85:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 for(ll i=0;i<nuj.size();i++)
            ~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 23800 KB Output is correct
2 Correct 21 ms 23912 KB Output is correct
3 Correct 21 ms 23980 KB Output is correct
4 Correct 21 ms 24236 KB Output is correct
5 Correct 27 ms 25016 KB Output is correct
6 Correct 36 ms 25676 KB Output is correct
7 Correct 36 ms 26700 KB Output is correct
8 Correct 50 ms 32076 KB Output is correct
9 Correct 124 ms 33732 KB Output is correct
10 Correct 197 ms 49532 KB Output is correct
11 Correct 190 ms 49532 KB Output is correct
12 Correct 387 ms 93536 KB Output is correct
13 Correct 540 ms 93536 KB Output is correct
14 Correct 289 ms 93536 KB Output is correct
15 Correct 449 ms 95012 KB Output is correct
16 Correct 730 ms 95012 KB Output is correct
17 Correct 554 ms 95012 KB Output is correct
18 Correct 212 ms 95012 KB Output is correct
19 Correct 403 ms 95012 KB Output is correct
20 Correct 294 ms 95012 KB Output is correct