Submission #1077352

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077352	2024-08-27T05:41:55 Z	komasan	Lozinke (COCI17_lozinke)	C++14	100 / 100	275 ms	17508 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	3 ms	344 KB	Output is correct
5	Correct	13 ms	708 KB	Output is correct
6	Correct	24 ms	604 KB	Output is correct
7	Correct	57 ms	860 KB	Output is correct
8	Correct	44 ms	1020 KB	Output is correct
9	Correct	42 ms	4196 KB	Output is correct
10	Correct	105 ms	8272 KB	Output is correct
11	Correct	75 ms	6628 KB	Output is correct
12	Correct	275 ms	16348 KB	Output is correct
13	Correct	118 ms	6480 KB	Output is correct
14	Correct	167 ms	16212 KB	Output is correct
15	Correct	254 ms	17508 KB	Output is correct
16	Correct	110 ms	5212 KB	Output is correct
17	Correct	24 ms	5212 KB	Output is correct
18	Correct	18 ms	5208 KB	Output is correct
19	Correct	157 ms	11088 KB	Output is correct
20	Correct	54 ms	5336 KB	Output is correct