Submission #237203

#	Time	Username	Problem	Language	Result	Execution time	Memory
237203		DIvanCode	Lozinke (COCI17_lozinke)	C++14	100 / 100	262 ms	16188 KiB

lozinke

#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<iomanip>

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define sz(v) (int) v.size()

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;

const int MAX_N = 2e4 + 5, MAX_LEN = 15;

int n;
string s[MAX_N];
vector<int> on_len[MAX_LEN];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	unordered_map<string, int> cnt;
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		cnt[s[i]]++;
		on_len[sz(s[i])].eb(i);
	}
	unordered_map<string, int> have;
	int ans = 0;
	for (int len = 10; len >= 1; --len) {
		for (int &i : on_len[len]) {
			ans += have[s[i]];
		}
		for (int &i : on_len[len]) {
			set<string> diff;
			for (int l = 0; l < sz(s[i]); ++l) {
				string curr;
				for (int r = l; r < min(sz(s[i]), l + len - 1); ++r) {
					curr.push_back(s[i][r]);
					diff.emplace(curr);
				}
			}
			for (string t : diff) {
				have[t]++;
			}
		}
	}
	for (int i = 1; i <= n; ++i) {
		ans += cnt[s[i]] - 1;
	}
	cout << ans << "\n";
	return 0;
}

• Subtask 1: 100 / 100