oj.uz

답안 #1077352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077352 2024-08-27T05:41:55 Z komasan Lozinke (COCI17_lozinke) C++14
100 / 100
 275 ms 17508 KB 
#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

# 결과 실행 시간 메모리 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