oj.uz

답안 #152937

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
152937 2019-09-10T14:52:22 Z phillip Lozinke (COCI17_lozinke) C++14
15 / 100
 65 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 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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 888 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Incorrect 3 ms 1016 KB Output isn't correct
4 Incorrect 3 ms 1016 KB Output isn't correct
5 Incorrect 5 ms 1528 KB Output isn't correct
6 Incorrect 7 ms 1628 KB Output isn't correct
7 Incorrect 8 ms 2424 KB Output isn't correct
8 Incorrect 8 ms 2936 KB Output isn't correct
9 Incorrect 24 ms 4472 KB Output isn't correct
10 Incorrect 32 ms 9208 KB Output isn't correct
11 Incorrect 35 ms 7160 KB Output isn't correct
12 Incorrect 53 ms 17016 KB Output isn't correct
13 Incorrect 59 ms 5880 KB Output isn't correct
14 Incorrect 53 ms 17528 KB Output isn't correct
15 Incorrect 64 ms 18424 KB Output isn't correct
16 Incorrect 65 ms 1528 KB Output isn't correct
17 Correct 28 ms 1016 KB Output is correct
18 Correct 26 ms 1016 KB Output is correct
19 Incorrect 53 ms 11640 KB Output isn't correct
20 Incorrect 44 ms 1528 KB Output isn't correct