/******************************
* author : @yayayaya *
* date : 21 / 10 / 2022 *
******************************/
/* (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ (≈ㅇᆽㅇ≈)♡ */
/*
/^--^\ /^--^\ /^--^\
\____/ \____/ \____/
/ \ / \ / \
| | | | | |
\__ __/ \__ __/ \__ __/
|^|^|^|^|^|^|^|^|^|^|^|^\ \^|^|^|^/ /^|^|^|^|^\ \^|^|^|^|^|^|^|^|^|^|^|^|
| | | | | | | | | | | | |\ \| | |/ /| | | | | |\ \| | | | | | | | | | | |
| | | | | | | | | | | | |/ /| | |\ \| | | | | |/ /| | | | | | | | | | | |
| | | | | | | | | | | | |\/ | | | \/| | | | | |\/ | | | | | | | | | | | |
#########################################################################
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | */
/*******************************************************************************************
* ################################################################# *
* # _` # *
* # _ooOoo_ # *
* # o8888888o # *
* # 88" . "88 # *
* # (| -_- |) # *
* # O\ = /O # *
* # ____/`---'\____ # *
* # .' \| |// `. # *
* # / \||| : |||// \ # *
* # / _||||| -:- |||||_ \ # *
* # | | \ - /'| | | # *
* # | \_| `\`---'// |_/ | # *
* # \ .-\__ `-. -'__/-. / # *
* # ___`. .' /--.--\ `. .'___ # *
* # ."" '< `.___\_<|>_/___.' _> \"". # *
* # | | : `- \`. ;`. _/; .'/ / .' ; | # *
* # \ \ `-. \_\_`. _.'_/_/ -' _.' / # *
* #=============`-.`___`-.__\ \___ /__.-'_.'_.-'=================# *
* `=--=-' *
* *
* /\_/\* *
* ( -.-) *
* _.-/`) / >O \>1 _.-/`) *
* // / / ) // / / ) *
* .=// / / / ) /\_/\ /\_/\ .=// / / / ) *
* //`/ / / / / ( -.-) ( -.-) //`/ / / / / *
* // / ` / / >O \>1 / >O \>1 // / ` / *
* \ / \ / *
* )) .' /\_/\ /\_/\ /\_/\ )) .' *
* // / ( -.-) ( -.-) ( -.-) // / *
* / / >O \>1 / >O \>1 / >O \>1 / *
* *
*******************************************************************************************/
#include <bits/stdc++.h>
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC optimize ("O3,unroll-loops,no-stack-protector")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))
#define FOR(i_, a_, b_) for(int i_ = (int) (a_); i_ <= (int) (b_); ++i_)
#define FORD(i_, a_, b_) for(int i_ = (int) (a_); i_ >= (int) (b_); --i_)
#define db(val) "["#val" = "<<(val)<<"] "
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
template<class X, class Y> bool minimize(X &x, const Y &y){
X eps = 1e-9;
if (x > y + eps) {
x = y;
return 1;
}
return 0;
}
template<class X, class Y> bool maximize(X &x, const Y &y) {
X eps = 1e-9;
if (x + eps < y) {
x = y;
return 1;
}
return 0;
}
template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }
const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 1e5 + 11;
const int LOG = (int) 20;
const ii dxy8[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1} };
const ii dxy4[] = { {-1, 0}, {1, 0}, {0, 1}, {0, -1} };
bool comp(const string &a, const string &b){
return ((int) a.size() < (int) b.size());
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define TASK "LOZINKE"
if(fopen(TASK".inp", "r")) {
freopen(TASK".inp", "r", stdin);
freopen(TASK".out", "w", stdout);
}
int n; cin >> n;
vector<string> str(n);
FOR(i, 0, n - 1) cin >> str[i];
sort(ALL(str), comp);
unordered_map<string, int> mp;
ll res = 0;
FOR(i, 0, n - 1){
string s = str[i];
unordered_map<string, bool> mark;
FOR(k, 1, (int) s.size() - 1){
for(int l = 0; l + k - 1 < (int) s.size(); l++){
string cur = s.substr(l, k);
if(mark.find(cur) == mark.end()){
if(mp.find(cur) != mp.end()){
res += (ll) mp[cur];
}
mark[cur] = 1;
}
}
}
mp[s]++;
}
for(auto x : mp) res += (ll) (x.second * (x.second - 1));
cout << res;
return 0;
}
/// CONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACOCONCACO ///
Compilation message
lozinke.cpp: In function 'int main()':
lozinke.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | freopen(TASK".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lozinke.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | freopen(TASK".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
324 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
5 ms |
332 KB |
Output is correct |
| 6 |
Correct |
8 ms |
464 KB |
Output is correct |
| 7 |
Correct |
10 ms |
504 KB |
Output is correct |
| 8 |
Correct |
12 ms |
512 KB |
Output is correct |
| 9 |
Correct |
51 ms |
1132 KB |
Output is correct |
| 10 |
Correct |
59 ms |
1200 KB |
Output is correct |
| 11 |
Correct |
64 ms |
1504 KB |
Output is correct |
| 12 |
Correct |
115 ms |
1664 KB |
Output is correct |
| 13 |
Correct |
135 ms |
2032 KB |
Output is correct |
| 14 |
Correct |
93 ms |
2252 KB |
Output is correct |
| 15 |
Correct |
127 ms |
2120 KB |
Output is correct |
| 16 |
Correct |
144 ms |
1176 KB |
Output is correct |
| 17 |
Correct |
48 ms |
1104 KB |
Output is correct |
| 18 |
Correct |
37 ms |
1108 KB |
Output is correct |
| 19 |
Correct |
102 ms |
1948 KB |
Output is correct |
| 20 |
Correct |
81 ms |
1204 KB |
Output is correct |
