Submission #80279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80279	2018-10-19T18:00:16 Z	fredbr	Lozinke (COCI17_lozinke)	C++17	100 / 100	160 ms	16320 KB

lozinke

#include <bits/stdc++.h>
 
using namespace std;
 
set<int> atuais;
int idx = 0;
 

struct Node
{
	int cnt = 0, id;
	vector<pair<char, Node*>> b;
 
	Node() {
		cnt = 0, id = ++idx;
	}
};
 
using tp = pair<char, Node*>;

Node root = Node();
 
void add(string const& s)
{
	Node* at = &root;
	for (char a : s) {
		auto it = find_if(at->b.begin(), at->b.end(),
			[a] (tp const& x) {return a == x.first;});

		if (it == at->b.end()) {
			at->b.push_back({a, new Node()});
			at = at->b.back().second;
		}
		else at = it->second;

		if (atuais.count(at->id) == 0) at->cnt++;
		atuais.insert(at->id);
	}
}
 
int cnt(string const& s)
{
	Node* at = &root;
	for (char a : s) {
		auto it = find_if(at->b.begin(), at->b.end(),
			[a] (tp const& x) {return a == x.first;});

		if (it == at->b.end()) return 0;
		at = it->second;
	}
	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	1112 KB	Output is correct
3	Correct	3 ms	1112 KB	Output is correct
4	Correct	3 ms	1112 KB	Output is correct
5	Correct	7 ms	1488 KB	Output is correct
6	Correct	9 ms	1488 KB	Output is correct
7	Correct	11 ms	2264 KB	Output is correct
8	Correct	18 ms	2976 KB	Output is correct
9	Correct	38 ms	2976 KB	Output is correct
10	Correct	80 ms	7656 KB	Output is correct
11	Correct	62 ms	7656 KB	Output is correct
12	Correct	147 ms	16320 KB	Output is correct
13	Correct	104 ms	16320 KB	Output is correct
14	Correct	104 ms	16320 KB	Output is correct
15	Correct	160 ms	16320 KB	Output is correct
16	Correct	115 ms	16320 KB	Output is correct
17	Correct	35 ms	16320 KB	Output is correct
18	Correct	27 ms	16320 KB	Output is correct
19	Correct	107 ms	16320 KB	Output is correct
20	Correct	62 ms	16320 KB	Output is correct