Submission #80267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80267	2018-10-19T17:06:32 Z	fredbr	Lozinke (COCI17_lozinke)	C++17	40 / 100	34 ms	20408 KB

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 = 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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	2 ms	564 KB	Output is correct
4	Correct	3 ms	676 KB	Output is correct
5	Correct	6 ms	1484 KB	Output is correct
6	Correct	8 ms	1484 KB	Output is correct
7	Correct	10 ms	3532 KB	Output is correct
8	Correct	14 ms	5836 KB	Output is correct
9	Runtime error	11 ms	5836 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	25 ms	13148 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	13 ms	13148 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	34 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	15 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	19 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	30 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	14 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	5 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	4 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	17 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	9 ms	20408 KB	Execution killed with signal 11 (could be triggered by violating memory limits)