Submission #241111

#	Time	Username	Problem	Language	Result	Execution time	Memory
241111		DavidDamian	Lozinke (COCI17_lozinke)	C++11	100 / 100	44 ms	23672 KiB

lozinke

#include <bits/stdc++.h>
using namespace std;
///Trie
///Determine the number of pairs that A can login as B
struct node
{
    int bucket[27];
    int wordCount;
    int last;
};
node trie[2000005];
int actNode=0;
void Insert(string s,int id)
{
    for(int a=0;a<s.size();a++){
        int u=0;
        for(int i=a;i<s.size();i++){
            int letter=s[i]-'a';
            if(trie[u].bucket[letter]==0)
                trie[u].bucket[letter]=++actNode;
            u=trie[u].bucket[letter];
            if(trie[u].last!=id) //Last hast to be different from actual string (that string can have the same substring
                                                                                    //but still the same person)
                trie[u].wordCount++;
            trie[u].last=id;
        }
    }
}
int query(string s) ///Return the number of other strings with the same substring than s
{
    int u=0;
    for(int i=0;i<s.size();i++){
        int letter=s[i]-'a';
        if(trie[u].bucket[letter]==0)
            return 0;
        u=trie[u].bucket[letter];
    }
    return trie[u].wordCount-1;
}
int n;
vector<string> A;
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        Insert(s,i);
        A.push_back(s);
    }
    int total=0;
    for(string s: A){
        total+=query(s);
    }
    cout<<total<<'\n';
    return 0;
}

Compilation message (stderr)

lozinke.cpp: In function 'void Insert(std::__cxx11::string, int)':
lozinke.cpp:15:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int a=0;a<s.size();a++){
                 ~^~~~~~~~~
lozinke.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=a;i<s.size();i++){
                     ~^~~~~~~~~
lozinke.cpp: In function 'int query(std::__cxx11::string)':
lozinke.cpp:32:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<s.size();i++){
                 ~^~~~~~~~~

• Subtask 1: 100 / 100