Submission #15795474


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u);
    }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r;
}
int getrandmax() {
    static uint32_t y = time(NULL);
    y ^= (y << 13); y ^= (y >> 17);
    y ^= (y << 5);
    return abs((int)y);
}
// [l, r]
int getrand(int l, int r) {
    return getrandmax() % (r - l + 1) + l;
}
typedef ModInt<1000000007> mint1;
typedef ModInt<1000000009> mint2;
int primes[10] = { 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093 };
bool isShuffle = false;
struct RollingHash {
    mint1 p1; mint2 p2;
    int n;
    vector<mint1> m1; vector<mint2> m2;
    vector<mint1> v1; vector<mint2> v2;
    vector<mint1> r1; vector<mint2> r2;

    RollingHash() {
        if (!isShuffle) {
            rep(i, 0, 101) { int a = getrand(0, 9); int b = getrand(0, 9); swap(primes[a], primes[b]); }
            isShuffle = true;
        }
        p1 = primes[0], p2 = primes[1];
    }

    void init(string s, char o = 'a') {
        vector<int> v;
        fore(c, s) v.push_back(c - o + 1);
        init(v);
    }

    void init(vector<int> s) {
        n = s.size();
        m1.resize(n); m2.resize(n); v1.resize(n); v2.resize(n); r1.resize(n); r2.resize(n);

        m1[0] = 1; m2[0] = 1;
        v1[0] = s[0]; v2[0] = s[0];

        rep(i, 1, n) {
            m1[i] = m1[i - 1] * p1;
            m2[i] = m2[i - 1] * p2;
            v1[i] = v1[i - 1] + m1[i] * s[i];
            v2[i] = v2[i - 1] + m2[i] * s[i];
        }

        r1[n - 1] = mint1(1) / m1[n - 1];
        rrep(i, n - 2, 0) r1[i] = r1[i + 1] * p1;

        r2[n - 1] = mint2(1) / m2[n - 1];
        rrep(i, n - 2, 0) r2[i] = r2[i + 1] * p2;
    }
    // s[l..r]
    inline pair<mint1, mint2> hash(int l, int r) {
        if (l > r) return { 0,0 };
        assert(l <= r); assert(r < n);
        mint1 a = v1[r];
        if (l) a -= v1[l - 1];
        a *= r1[l];

        mint2 b = v2[r];
        if (l) b -= v2[l - 1];
        b *= r2[l];

        return { a, b };
    }
    // s[l..r]
	inline ll llhash(int l, int r) {
		auto h = hash(l, r);
		return 1LL * h.first.get() * h.second.Mod + h.second.get();
	}
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     @hamayanhamayan0
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/














int N;
string S[201010];
map<ll, int> cnt[26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) reverse(all(S[i]));
    sort(S, S + N, [&](string a, string b) { return a.length() < b.length(); });

    ll ans = 0;
    
    RollingHash rh;
    rep(i, 0, N) {
        rh.init(S[i]);
        int n = S[i].length();
        
        int msk = 0;
        rrep(j, n - 1, 0) {
            msk |= (1 << (S[i][j] - 'a'));
            ll hh = rh.llhash(0, j - 1);
            rep(c, 0, 26) if ((msk & (1 << c)) && cnt[c].count(hh)) {
                ans += cnt[c][hh];
            }
        }

        ll h = rh.llhash(0, n - 2);
        cnt[S[i][n - 1] - 'a'][h]++;
    }

    cout << ans << endl;
}





Submission Info

Submission Time
Task B - First Second
User hamayanhamayan
Language C++ (GCC 9.2.1)
Score 700
Code Size 5774 Byte
Status AC
Exec Time 1677 ms
Memory 43076 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 2
AC × 26
Set Name Test Cases
Sample s1.txt, s2.txt
All 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
001.txt AC 12 ms 9908 KB
002.txt AC 10 ms 9784 KB
003.txt AC 12 ms 9760 KB
004.txt AC 41 ms 10324 KB
005.txt AC 324 ms 13884 KB
006.txt AC 1419 ms 43076 KB
007.txt AC 1677 ms 36736 KB
008.txt AC 664 ms 22392 KB
009.txt AC 397 ms 15396 KB
010.txt AC 1361 ms 12128 KB
011.txt AC 455 ms 11076 KB
012.txt AC 653 ms 20384 KB
013.txt AC 870 ms 27256 KB
014.txt AC 528 ms 30972 KB
015.txt AC 358 ms 14688 KB
016.txt AC 1010 ms 11568 KB
017.txt AC 251 ms 11400 KB
018.txt AC 782 ms 11180 KB
019.txt AC 1219 ms 11440 KB
020.txt AC 799 ms 18672 KB
021.txt AC 471 ms 13584 KB
022.txt AC 364 ms 11400 KB
023.txt AC 100 ms 11208 KB
024.txt AC 1123 ms 11160 KB
s1.txt AC 12 ms 9780 KB
s2.txt AC 10 ms 9908 KB