oj.uz

Submission #445139

# Submission time Handle Problem Language Result Execution time Memory
445139 2021-07-16T14:51:03 Z Killer2501 Lozinke (COCI17_lozinke) C++14
30 / 100
 453 ms 24168 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] = p[i-1] * base % mod;
        p1[i] = 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
30.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11280 KB Output isn't correct
2 Correct 8 ms 11212 KB Output is correct
3 Incorrect 8 ms 11340 KB Output isn't correct
4 Correct 8 ms 11340 KB Output is correct
5 Incorrect 14 ms 11800 KB Output isn't correct
6 Incorrect 20 ms 12072 KB Output isn't correct
7 Incorrect 22 ms 12312 KB Output isn't correct
8 Correct 31 ms 12816 KB Output is correct
9 Incorrect 75 ms 15044 KB Output isn't correct
10 Incorrect 141 ms 17320 KB Output isn't correct
11 Incorrect 155 ms 17564 KB Output isn't correct
12 Correct 453 ms 24168 KB Output is correct
13 Incorrect 269 ms 18120 KB Output isn't correct
14 Incorrect 293 ms 22900 KB Output isn't correct
15 Incorrect 432 ms 24136 KB Output isn't correct
16 Incorrect 220 ms 12368 KB Output isn't correct
17 Correct 82 ms 11852 KB Output is correct
18 Correct 55 ms 11804 KB Output is correct
19 Incorrect 269 ms 19936 KB Output isn't correct
20 Incorrect 100 ms 12272 KB Output isn't correct