oj.uz

Submission #585941

# Submission time Handle Problem Language Result Execution time Memory
585941 2022-06-29T15:07:57 Z MilosMilutinovic Lozinke (COCI17_lozinke) C++14
100 / 100
 270 ms 13504 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int B1 = 453571;
const int MOD1 = 1e9 + 9;
const int B2 = 744313;
const int MOD2 = 1e9 + 7;

const int N = 20020;
string s[N];
int n;

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> s[i];
	sort(s, s + n, [&](string a, string b) {
		if (a.size() != b.size())
			return a.size() < b.size();
		return a < b;
	});
	map<pii, int> cnt;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int m = (int)s[i].size();
		ll myHash1 = 0;
		ll myHash2 = 0;
		set<pair<ll, ll>> st;
		for (int l = 0; l < m; l++) {
			ll hsh1 = 0, hsh2 = 0;
			for (int r = l; r < m; r++) {
				hsh1 = hsh1 * B1 + (s[i][r] - 'a' + 1);
				hsh1 %= MOD1; 
				hsh2 = hsh2 * B2 + (s[i][r] - 'a' + 1);
				hsh2 %= MOD2; 
				st.insert(mp(hsh1, hsh2));
			}
			if (l == 0) 
				myHash1 = hsh1, myHash2 = hsh2;
		}
		for (auto p : st)
			ans += cnt[p];
		cnt[mp(myHash1, myHash2)]++;		
	}
	for (auto& p : cnt) {
		ans += (ll)p.second * (p.second - 1) / 2;
	}
	printf("%lld", ans);

	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 2 ms 852 KB Output is correct
3 Correct 1 ms 952 KB Output is correct
4 Correct 2 ms 980 KB Output is correct
5 Correct 6 ms 1268 KB Output is correct
6 Correct 12 ms 1212 KB Output is correct
7 Correct 18 ms 1748 KB Output is correct
8 Correct 23 ms 2388 KB Output is correct
9 Correct 47 ms 2316 KB Output is correct
10 Correct 126 ms 6464 KB Output is correct
11 Correct 84 ms 3780 KB Output is correct
12 Correct 270 ms 13504 KB Output is correct
13 Correct 120 ms 2444 KB Output is correct
14 Correct 200 ms 12236 KB Output is correct
15 Correct 255 ms 13380 KB Output is correct
16 Correct 75 ms 1140 KB Output is correct
17 Correct 31 ms 980 KB Output is correct
18 Correct 26 ms 1084 KB Output is correct
19 Correct 172 ms 7124 KB Output is correct
20 Correct 49 ms 1092 KB Output is correct