oj.uz

Submission #472799

# Submission time Handle Problem Language Result Execution time Memory
472799 2021-09-14T10:51:11 Z AbdoMo Lozinke (COCI17_lozinke) C++17
100 / 100
 460 ms 18352 KB 
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
const int mod = 1e9+7;
using namespace std;
bool comp(string a,string b)
{
    if(a.size()==b.size())
    {
        return a<b;
    }
    return a.size()<b.size();
}
void solve(){
    int n;
    cin>>n;
    vector<string>v;
    map<string,int>freq;
    map<string,int>freqsb;
    set<string,decltype(comp)*>st(comp);
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        st.insert(s);
        set<string>ts;
        for(int j=0;j<s.size();j++)
        {
            for(int k=1;k+j<=s.size();k++)
            {
                ts.insert(s.substr(j,k));
            }
        }
        for(auto it=ts.begin();it!=ts.end();it++)
        {
            freqsb[*it]++;
        }
        freq[s]++;
        v.pb(s);
    }
    sort(v.begin(),v.end(),comp);
    int ans=0;
    int c=1;
    auto it=st.begin();
    for(int i=0;i<n;i+=freq[v[i]],it++)
    {
        auto j=it;
        j++;
        int x=freq[v[i]];
        ans+=x*(x-1);
        ans+=freq[v[i]]*(freqsb[v[i]]-freq[v[i]]);

    }
    cout<<ans<<endl;
    /*

    */

}
int32_t main(){
	int t=1;
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //cin>>t;
	while(t--){solve();}
	return 0;
}

Compilation message

lozinke.cpp: In function 'void solve()':
lozinke.cpp:28:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j=0;j<s.size();j++)
      |                     ~^~~~~~~~~
lozinke.cpp:30:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |             for(int k=1;k+j<=s.size();k++)
      |                         ~~~^~~~~~~~~~
lozinke.cpp:44:9: warning: unused variable 'c' [-Wunused-variable]
   44 |     int c=1;
      |         ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 11 ms 840 KB Output is correct
6 Correct 18 ms 804 KB Output is correct
7 Correct 24 ms 1580 KB Output is correct
8 Correct 35 ms 2492 KB Output is correct
9 Correct 100 ms 3260 KB Output is correct
10 Correct 201 ms 8468 KB Output is correct
11 Correct 175 ms 5684 KB Output is correct
12 Correct 435 ms 17992 KB Output is correct
13 Correct 285 ms 4672 KB Output is correct
14 Correct 339 ms 17500 KB Output is correct
15 Correct 460 ms 18352 KB Output is correct
16 Correct 268 ms 1708 KB Output is correct
17 Correct 75 ms 1396 KB Output is correct
18 Correct 59 ms 1344 KB Output is correct
19 Correct 365 ms 10436 KB Output is correct
20 Correct 156 ms 1732 KB Output is correct