oj.uz

답안 #1077356

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1077356 2024-08-27T05:48:09 Z trvhung Lozinke (COCI17_lozinke) C++17
100 / 100
 240 ms 17488 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 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