oj.uz

Submission #237203

# Submission time Handle Problem Language Result Execution time Memory
237203 2020-06-05T08:51:51 Z DIvanCode Lozinke (COCI17_lozinke) C++14
100 / 100
 262 ms 16188 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<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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 6 ms 1024 KB Output is correct
5 Correct 12 ms 1408 KB Output is correct
6 Correct 15 ms 1408 KB Output is correct
7 Correct 17 ms 2304 KB Output is correct
8 Correct 23 ms 2816 KB Output is correct
9 Correct 60 ms 3068 KB Output is correct
10 Correct 107 ms 7816 KB Output is correct
11 Correct 96 ms 4904 KB Output is correct
12 Correct 261 ms 16156 KB Output is correct
13 Correct 177 ms 3704 KB Output is correct
14 Correct 185 ms 15192 KB Output is correct
15 Correct 262 ms 16188 KB Output is correct
16 Correct 209 ms 1408 KB Output is correct
17 Correct 124 ms 1152 KB Output is correct
18 Correct 87 ms 1272 KB Output is correct
19 Correct 166 ms 8964 KB Output is correct
20 Correct 109 ms 1408 KB Output is correct