Submission #152937

#	Time	Username	Problem	Language	Result	Execution time	Memory
152937		phillip	Lozinke (COCI17_lozinke)	C++14	15 / 100	65 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 ret=0;
void query(Trie *node,int pos,string s){
        ret+=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];
    //
    // cout<<query(root,0,a);
    sort(s,s+n,cmp);
    //for(int i=0;i<n;i++)cout<<s[i]<<"\n";
    int ans=0,sum=0,s2;
    for(int i=0;i<n;i++)
    {
        sum=1;
        while(s[i]==s[i+1])
        {
            sum++;
            i++;
        }
  //      cout<<sum<<" ";
        ans+=(sum-1)*sum;
        int ls=s[i].size();
        s2=0;
        for(int j=0;j<s[i].size();j++)
        {
            ret=0;
            query(root,0,s[i].substr(j,ls));
            s2+=ret;
        }
        for(int j=0;j<s[i].size();j++)
        {
            ret=0;
            rb(root,0,s[i].substr(j,ls));
            //s2+=ret;
        }
        ans+=s2*sum;
    //    cout<<ans<<"\n";
        for(int j=0;j<sum;j++)insert(root,0,s[i]);
    }
    cout<<ans;
}

/*
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:78: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:95: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:106:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size())
            ~~~~^~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:143:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<s[i].size();j++)
                     ~^~~~~~~~~~~~
lozinke.cpp:149:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<s[i].size();j++)
                     ~^~~~~~~~~~~~

• Subtask 1: 15 / 100