Submission #1077356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077356		trvhung	Lozinke (COCI17_lozinke)	C++17	100 / 100	240 ms	17488 KiB

lozinke

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define ll long long
#define el '\n'

const int maxn = 2e4 + 5;
const ll base = 31;
int n, strSz[maxn];
string s;
ll H[maxn][15][2], mods[2], pw[2][15];

pair<ll, ll> get(int id, int l, int r) {
	pair<ll, ll> res;
	res.F = (H[id][r][0] - H[id][l - 1][0] * pw[0][r - l + 1] + mods[0] * mods[0]) % mods[0];
	res.S = (H[id][r][1] - H[id][l - 1][1] * pw[1][r - l + 1] + mods[1] * mods[1]) % mods[1];
	return res;
}

void preprocess() {
	mods[0] = 1e9 + 10777, mods[1] = 1e9 + 19777;

	for (int j = 0; j < 2; ++j) {
		pw[j][0] = 1;
		for (int i = 1; i <= 10; ++i)
			pw[j][i] = pw[j][i - 1] * base % mods[j];
	}

	for (int t = 1; t <= n; ++t) {
		cin >> s;

		int sz = s.size(); strSz[t] = sz; s = ' ' + s;
		for (int j = 0; j < 2; ++j)
			for (int i = 1; i <= sz; ++i)
				H[t][i][j] = (H[t][i - 1][j] * base + s[i] - 'a' + 1) % mods[j];
	}
}

void oneSolve() {

	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		pair<ll, ll> cur = get(i, 1, strSz[i]);

		for (int j = 1; j <= n; ++j) {
			if (i == j) continue;

			bool c = false;
			for (int k = 1; k + strSz[i] - 1 <= strSz[j]; ++k) {
				pair<ll, ll> gt = get(j, k, k + strSz[i] - 1);
				if (gt.F == cur.F && gt.S == cur.S) {
					c = true;
					break;
				}
			}	

			if (c) ans++;
		}
	}

	cout << ans;

}

void twoSolve() {

	map<pair<ll, ll>, int> cnt, hav;
	for (int t = 1; t <= n; ++t) {
		int sz = strSz[t];

		hav.clear();
		for (int i = 1; i <= sz; ++i)
			for (int j = i; j <= sz; ++j) {
				pair<ll, ll> gt = get(t, i, j);
				if (hav.find(gt) != hav.end()) continue;
				hav[gt] = 1; 

				if (cnt.find(gt) == cnt.end()) cnt[gt] = 1;
				else cnt[gt]++;
			}
	}

	int ans = 0;
	for (int t = 1; t <= n; ++t) {
		pair<ll, ll> gt = get(t, 1, strSz[t]);
		ans += cnt[gt] - 1;
	}

	cout << ans;

}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> n;

	preprocess();

	if (n <= 2000) oneSolve();
	else twoSolve();

	return 0;
}

• Subtask 1: 100 / 100