Submission #80270

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
80270	2018-10-19T17:09:08 Z	fredbr	Lozinke (COCI17_lozinke)	C++17	40 / 100	35 ms	12124 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 = 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	548 KB	Output is correct
3	Correct	3 ms	680 KB	Output is correct
4	Correct	3 ms	680 KB	Output is correct
5	Correct	7 ms	1272 KB	Output is correct
6	Correct	10 ms	1272 KB	Output is correct
7	Correct	12 ms	2228 KB	Output is correct
8	Correct	18 ms	3636 KB	Output is correct
9	Runtime error	11 ms	3636 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	24 ms	7964 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	14 ms	7964 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	35 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	16 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
14	Runtime error	21 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Runtime error	28 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
16	Runtime error	17 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
17	Runtime error	6 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
18	Runtime error	6 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
19	Runtime error	18 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
20	Runtime error	9 ms	12124 KB	Execution killed with signal 11 (could be triggered by violating memory limits)