# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
80273 | fredbr | Lozinke (COCI17_lozinke) | C++17 | 226 ms | 26352 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
set<int> atuais;
int idx = 0;
struct Node
{
int cnt = 0, id;
map<char, Node*> b;
Node() {
cnt = 0, id = ++idx;
}
};
Node root = Node();
void add(string const& s)
{
Node* at = &root;
for (char a : s) {
if (at->b.find(a-'a')==at->b.end()) at->b[a-'a'] = new Node();
at = at->b[a-'a'];
if (atuais.count(at->id) == 0) at->cnt++;
atuais.insert(at->id);
}
}
int cnt(string const& s)
{
Node* at = &root;
for (char a : s) {
if (at->b.find(a-'a')==at->b.end()) return 0;
at = at->b[a-'a'];
}
return at->cnt;
}
string subs(string const& s, int l, int r)
{
string ans;
for (int i = l; i < r; i++)
ans.push_back(s[i]);
return ans;
}
const int maxn = 20202;
string v[maxn];
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> v[i];
string& s = v[i];
for (int j = 0; j < int(s.size()); j++)
add(subs(s, j, s.size()));
atuais.clear();
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans += cnt(v[i])-1;
}
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |