oj.uz

Submission #152939

# Submission time Handle Problem Language Result Execution time Memory
152939 2019-09-10T15:04:52 Z phillip Lozinke (COCI17_lozinke) C++14
100 / 100
 86 ms 18424 KB 
/*#include <bits/stdc++.h>

using namespace std;
long long the,n;
string s[100004];
struct trie
{
    int en=0,cnt=0;
    trie *a[27]={0};
    void inse(int x,int y)
    {

        if (y==s[x].size())
        {
            en++;
            cnt++;
            return;
        }
        int ind=s[x][y]-'a';
        if (a[ind]==0) a[ind]=new trie;
        a[ind]->inse(x,y+1);
    }
    void ans(int x,int y)
    {
        the+=en;
        en=0;
        if (y==s[x].size()) return ;
        if (a[s[x][y]-'a']!=0) a[s[x][y]-'a']->ans(x,y+1);
        return ;
    }
    void rep(int x,int y)
    {
        en=cnt;
        if (y==s[x].size()) return ;
        if (a[s[x][y]-'a']!=0) a[s[x][y]-'a']->rep(x,y+1);
        return ;
    }
};
trie tr;
int main()
{
    cin>>n;
    for (int i=0;i<n;i++)
    {
        cin>>s[i];
        tr.inse(i,0);
    }
    for (int i=0;i<n;i++)
    {
            for (int j=0;j<s[i].size();j++) tr.ans(i,j);
            for (int j=0;j<s[i].size();j++) tr.rep(i,j);
    }
    cout<<the-n;
    return 0;
}


*/
#include <bits/stdc++.h>
using namespace std;

struct Trie{

    int cnt,ed,ored ;
    Trie *a[29];
    Trie(){
        cnt = 0;
        ed=0;
        ored=0;
        for(int i=0;i<29;i++)
            a[i] = 0;
    }
};

void insert(Trie *node,int pos,string s){
        node->cnt++;
        if(pos == s.size())
        {
            node->ored++;
            node->ed++;
            return ;
        }

        int num = s[pos]-'a';
        if(node->a[num] == 0)
            node->a[num] = new Trie();

        insert(node->a[num],pos+1,s);
    }
int ans=0;
void query(Trie *node,int pos,string s){
        ans+=node->ed;
        node->ed=0;
        if(pos == s.size())
        {
            return;
        }
         int num = s[pos]-'a';
         if(node->a[num] == 0)
            return;
         query(node->a[num],pos+1,s);
}
void rb(Trie *node,int pos,string s){
        node->ed=node->ored;
        if(pos == s.size())
            return;
         int num = s[pos]-'a';
         if(node->a[num] == 0)
            return;
         node->ed=node->ored;
         rb(node->a[num],pos+1,s);
}
Trie *root = new Trie();
bool cmp(string a,string b)
{
    if(a.size()<b.size())return true;
    return false;
}
int n;
string s[20009];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>s[i];
        insert(root,0,s[i]);
    }
    //
    // cout<<query(root,0,a);
    //sort(s,s+n,cmp);
    //for(int i=0;i<n;i++)cout<<s[i]<<"\n";
    for(int i=0;i<n;i++)
    {
        int ls=s[i].size();
        for(int j=0;j<s[i].size();j++)
        {
            query(root,0,s[i].substr(j,ls));
        }
        for(int j=0;j<s[i].size();j++)
        {
            rb(root,0,s[i].substr(j,ls));
            //s2+=ret;
        }
    //    cout<<ans<<"\n";
    }
    cout<<ans-n;
}

/*
10
ss
ssw
sss
sss
ssss
wwww
wwwwww
swswwww
aassswwe
wwwsssww*/

Compilation message

lozinke.cpp: In function 'void insert(Trie*, int, std::__cxx11::string)':
lozinke.cpp:77:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size())
            ~~~~^~~~~~~~~~~
lozinke.cpp: In function 'void query(Trie*, int, std::__cxx11::string)':
lozinke.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size())
            ~~~~^~~~~~~~~~~
lozinke.cpp: In function 'void rb(Trie*, int, std::__cxx11::string)':
lozinke.cpp:105:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size())
            ~~~~^~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:136:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<s[i].size();j++)
                     ~^~~~~~~~~~~~
lozinke.cpp:140:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<s[i].size();j++)
                     ~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1016 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 1144 KB Output is correct
5 Correct 5 ms 1528 KB Output is correct
6 Correct 7 ms 1656 KB Output is correct
7 Correct 7 ms 2424 KB Output is correct
8 Correct 8 ms 2936 KB Output is correct
9 Correct 23 ms 4528 KB Output is correct
10 Correct 36 ms 9208 KB Output is correct
11 Correct 39 ms 7164 KB Output is correct
12 Correct 62 ms 17028 KB Output is correct
13 Correct 56 ms 5852 KB Output is correct
14 Correct 55 ms 17656 KB Output is correct
15 Correct 86 ms 18424 KB Output is correct
16 Correct 59 ms 1656 KB Output is correct
17 Correct 61 ms 1016 KB Output is correct
18 Correct 47 ms 1016 KB Output is correct
19 Correct 56 ms 11528 KB Output is correct
20 Correct 39 ms 1528 KB Output is correct