Submission #1077356

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1077356	2024-08-27T05:48:09 Z	trvhung	Lozinke (COCI17_lozinke)	C++17	100 / 100	240 ms	17488 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	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	348 KB	Output is correct
5	Correct	13 ms	2696 KB	Output is correct
6	Correct	24 ms	600 KB	Output is correct
7	Correct	57 ms	924 KB	Output is correct
8	Correct	40 ms	856 KB	Output is correct
9	Correct	45 ms	4236 KB	Output is correct
10	Correct	106 ms	8272 KB	Output is correct
11	Correct	73 ms	6588 KB	Output is correct
12	Correct	233 ms	16600 KB	Output is correct
13	Correct	127 ms	6476 KB	Output is correct
14	Correct	167 ms	16208 KB	Output is correct
15	Correct	240 ms	17488 KB	Output is correct
16	Correct	108 ms	5320 KB	Output is correct
17	Correct	20 ms	5212 KB	Output is correct
18	Correct	18 ms	5212 KB	Output is correct
19	Correct	154 ms	11300 KB	Output is correct
20	Correct	53 ms	5212 KB	Output is correct