oj.uz

Submission #50298

# Submission time Handle Problem Language Result Execution time Memory
50298 2018-06-09T18:07:03 Z computerbox Lozinke (COCI17_lozinke) C++14
40 / 100
 857 ms 36944 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 2000

using namespace std;

set<ll>leaf[20010];
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
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1520 KB Output is correct
3 Correct 5 ms 1520 KB Output is correct
4 Correct 4 ms 1632 KB Output is correct
5 Incorrect 13 ms 2588 KB Output isn't correct
6 Incorrect 34 ms 3328 KB Output isn't correct
7 Incorrect 33 ms 3740 KB Output isn't correct
8 Runtime error 7 ms 4268 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 174 ms 12804 KB Output isn't correct
10 Runtime error 27 ms 12804 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 219 ms 20584 KB Output isn't correct
12 Runtime error 8 ms 20584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Incorrect 594 ms 32140 KB Output isn't correct
14 Runtime error 6 ms 32140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 7 ms 32140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Correct 857 ms 36944 KB Output is correct
17 Correct 592 ms 36944 KB Output is correct
18 Correct 221 ms 36944 KB Output is correct
19 Runtime error 47 ms 36944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Correct 364 ms 36944 KB Output is correct