Submission #152939

#	Time	Username	Problem	Language	Result	Execution time	Memory
152939		phillip	Lozinke (COCI17_lozinke)	C++14	100 / 100	86 ms	18424 KiB

lozinke

/*#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 (stderr)

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 / 100