Submission #236872

#	Time	Username	Problem	Language	Result	Execution time	Memory
236872		DanShaders	Lozinke (COCI17_lozinke)	C++17	100 / 100	227 ms	3064 KiB

lozinke

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,ssse3,sse4.1,sse4.2,avx,avx2")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

#define all(x) begin(x), end(x)
#define x first
#define y second
typedef long long ll;
typedef long double ld;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T>
using normal_queue = priority_queue<T, vector<T>, greater<T>>;

vector<string> strs;

vector<pair<string, int>> data_;

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		string s;
		cin >> s;
		strs.push_back(s);
	}
	sort(all(strs));
	for (int i = 0; i < n; ) {
		int st = i;
		while (i < n && strs[i] == strs[st])
			++i;
		data_.push_back({strs[st], i - st});
	}
	int64_t ans = 0;
	for (auto g : data_) {
		string s = g.x;
		int sz = (int) s.size();
		set<string> ss;
		for (int j = 0; j < sz; ++j)
			for (int h = 1; h <= sz - j; ++h)
				ss.insert(s.substr(j, h));
		for (string t : ss) {
			auto q = lower_bound(all(data_), pair<string, int>{t, -1});
			if (q != data_.end() && q->x == t)
				ans += q->y * g.y;
		}
	}
	cout << ans - n << "\n";
	return 0;
}

• Subtask 1: 100 / 100