Submission #652178

#	Time	Username	Problem	Language	Result	Execution time	Memory
652178		4EVER	Lozinke (COCI17_lozinke)	C++11	100 / 100	144 ms	2252 KiB

lozinke

/******************************
*    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 (stderr)

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);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100