Submission #80272

#	Time	Username	Problem	Language	Result	Execution time	Memory
80272		fredbr	Lozinke (COCI17_lozinke)	C++17	100 / 100	153 ms	45104 KiB

lozinke

#include <bits/stdc++.h>
 
using namespace std;
 
set<int> atuais;
int idx = 0;
 
struct Node
{
	int cnt = 0, id;
	Node* b[26];
 
	Node() {
		cnt = 0, id = ++idx;
		fill(b, b+26, nullptr);
	}
};
 
Node root = Node();
 
void add(string const& s)
{
	Node* at = &root;
	for (char a : s) {
		if (!at->b[a-'a']) 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[a-'a']) 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 / 100