Submission #80273

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80273	2018-10-19T17:20:23 Z	fredbr	Lozinke (COCI17_lozinke)	C++17	100 / 100	226 ms	26352 KB

lozinke

#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";
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1016 KB	Output is correct
2	Correct	3 ms	1260 KB	Output is correct
3	Correct	3 ms	1292 KB	Output is correct
4	Correct	3 ms	1292 KB	Output is correct
5	Correct	8 ms	1628 KB	Output is correct
6	Correct	10 ms	1648 KB	Output is correct
7	Correct	15 ms	2796 KB	Output is correct
8	Correct	25 ms	4136 KB	Output is correct
9	Correct	56 ms	4136 KB	Output is correct
10	Correct	100 ms	12140 KB	Output is correct
11	Correct	75 ms	12140 KB	Output is correct
12	Correct	219 ms	26352 KB	Output is correct
13	Correct	111 ms	26352 KB	Output is correct
14	Correct	143 ms	26352 KB	Output is correct
15	Correct	226 ms	26352 KB	Output is correct
16	Correct	123 ms	26352 KB	Output is correct
17	Correct	43 ms	26352 KB	Output is correct
18	Correct	29 ms	26352 KB	Output is correct
19	Correct	150 ms	26352 KB	Output is correct
20	Correct	67 ms	26352 KB	Output is correct