oj.uz

Submission #445141

# Submission time Handle Problem Language Result Execution time Memory
445141 2021-07-16T14:53:17 Z Killer2501 Lozinke (COCI17_lozinke) C++14
100 / 100
 460 ms 23872 KB 
#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define pii pair<ll, pll>
using namespace std;
using ll = int;
const int  N = 2e5+55;
const ll mod = 1e9+7;
const ll mod1 = 1e9+1;
const ll base = 311;
const ll base1 = 331;
ll m, n, t, k, a[N], tong, b[N], p[12], p1[12], c[N], lab[N], cnt;
long long ans;
string s[N];
vector<ll> adj[N];
vector<pll> e;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

void dfs(ll u)
{
    b[u] = 1;
    for(ll v : adj[u])
    {
        dfs(v);
        b[u] = b[u] * (b[v] + 1) % mod;

    }
    //cout << u << " " << b[u][0] <<" "<<b[u][1] << '\n';
}
void cal(ll u, ll sum)
{
    a[u] = sum * b[u] % mod;
    for(ll v : adj[u])
    {
        cal(v, a[u] * pw(b[v]+1, mod-2) % mod + 1);
    }
}
pll findp(ll u)
{
    if(lab[u] < 0)return {0, u};
    pll x = findp(lab[u]);
    x.fi += a[u];
    return x;
}
void hop(pll u, pll v, ll w)
{
    if(lab[u.se] > lab[v.se])
    {
        swap(u, v);
        w = -w;
    }
    lab[u.se] += lab[v.se];
    lab[v.se] = u.se;
    b[u.se] |= b[v.se];
    a[v.se] += w - v.fi + u.fi;
}

map<pll, ll> mp, ok;
ll get(ll l, ll r)
{
    return ( a[r] - 1ll * a[l-1] * p[r-l+1] % mod + mod) % mod;
}
ll get1(ll l, ll r)
{
    return ( b[r] - 1ll * b[l-1] * p1[r-l+1] % mod1 + mod1) % mod1;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> s[i];
        e.pb({s[i].length(), i});
    }
    p[0] = p1[0] = 1;
    for(int i = 1; i <= 10; i ++)
    {
        p[i] = 1ll * p[i-1] * base % mod;
        p1[i] = 1ll * p1[i-1] * base1 % mod1;
    }
    sort(e.begin(), e.end());
    for(int i = 0; i < n; i ++)
    {
        int id = e[i].se;
        m = e[i].fi;
        for(int j = 1; j <= m; j ++)
        {
            a[j] = (1ll * a[j-1] * base % mod + (s[id][j-1] - 'a' + 2)) % mod;
            b[j] = (1ll * b[j-1] * base1 % mod1 + (s[id][j-1] - 'a' + 2)) % mod1;
        }
        ok.clear();
        for(int l = 1; l <= m; l ++)
        {
            for(int r = l; r <= m; r ++)
            {
                if(ok[{get(l, r), get1(l, r)}] == 0)
                {
                    ok[{get(l, r), get1(l, r)}] = 1;
                    ans += mp[{get(l, r), get1(l, r)}];
                    if(l == 1 && r == m)ans += mp[{get(l, r), get1(l, r)}];
                }
            }
        }
        ++mp[{a[m], b[m]}];
    }
    cout << ans;
}
/*
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1
1 5 6
1 1 2 2
1 2 4 3
2 1 4
1 1 5 6
1 2 3 -2
2 3 5
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11212 KB Output is correct
2 Correct 6 ms 11296 KB Output is correct
3 Correct 6 ms 11212 KB Output is correct
4 Correct 7 ms 11340 KB Output is correct
5 Correct 13 ms 11508 KB Output is correct
6 Correct 16 ms 11524 KB Output is correct
7 Correct 20 ms 12148 KB Output is correct
8 Correct 30 ms 12848 KB Output is correct
9 Correct 63 ms 12748 KB Output is correct
10 Correct 177 ms 16760 KB Output is correct
11 Correct 115 ms 14060 KB Output is correct
12 Correct 460 ms 23872 KB Output is correct
13 Correct 174 ms 12868 KB Output is correct
14 Correct 284 ms 22676 KB Output is correct
15 Correct 397 ms 23752 KB Output is correct
16 Correct 186 ms 11596 KB Output is correct
17 Correct 41 ms 11596 KB Output is correct
18 Correct 35 ms 11680 KB Output is correct
19 Correct 190 ms 17496 KB Output is correct
20 Correct 83 ms 11596 KB Output is correct