Submission #80270

#	Time	Username	Problem	Language	Result	Execution time	Memory
80270		fredbr	Lozinke (COCI17_lozinke)	C++17	40 / 100	35 ms	12124 KiB

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 = 2020;

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: 40 / 100