Submission #152929

#	Time	Username	Problem	Language	Result	Execution time	Memory
152929		phillip	Lozinke (COCI17_lozinke)	C++14	10 / 100	67 ms	23900 KiB

lozinke

#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())
            return ;

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

        insert(node->a[num],pos+1,s);
        if(pos == s.size()-1)
        {
            node->ored++;
            node->ed++;
        }
    }
int ret=0;
void query(Trie *node,int pos,string s){

        if(pos == s.size())
            return;
         int num = s[pos]-'a';
         if(node->a[num] == 0)
            return;
         ret+=node->ed;
         node->ed=0;
         query(node->a[num],pos+1,s);
}
void rb(Trie *node,int pos,string s){

        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[200009];
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)cin>>s[i];
    //
    // cout<<query(root,0,a);
    sort(s,s+n,cmp);
    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<<"\n";
        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);
        for(int j=0;j<sum;j++)insert(root,0,s[i]);
    }
    cout<<ans;
}

Compilation message (stderr)

lozinke.cpp: In function 'void insert(Trie*, int, std::__cxx11::string)':
lozinke.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size())
            ~~~~^~~~~~~~~~~
lozinke.cpp:30:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size()-1)
            ~~~~^~~~~~~~~~~~~
lozinke.cpp: In function 'void query(Trie*, int, std::__cxx11::string)':
lozinke.cpp:39: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:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(pos == s.size())
            ~~~~^~~~~~~~~~~
lozinke.cpp: In function 'int main()':
lozinke.cpp:87:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<s[i].size();j++)
                     ~^~~~~~~~~~~~
lozinke.cpp:93:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<s[i].size();j++)
                     ~^~~~~~~~~~~~

• Subtask 1: 10 / 100