oj.uz

Submission #878820

# Submission time Handle Problem Language Result Execution time Memory
878820 2023-11-25T09:31:05 Z underwaterkillerwhale Lampice (COCI19_lampice) C++14
110 / 110
 1971 ms 15640 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define rep(i,m,n) for(int i=m; i<=n; i++)
#define reb(i,m,n) for(int i=m; i>=n; i--)
#define iter(id, v) for (auto id : v)
#define ii pair<int,int>
#define fs first
#define se second
#define pb push_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
#define el cout <<"\n"

template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v) { out << "(" << v.fs <<"," << v.se << ") "; return out; }

//#ifndef ONLINE_JUDGE
//    #include "debug.h"
//#else
//    #define deb(...) 23
//    #define ____
//#endif

mt19937 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const ll N = 5e4 + 7;
const ll Mod = 1e9 + 7;
const ll bse = 137;
const ll szBL = 650;
const ll INF = 2e9;

int n, m;

int a[N];

int nChild[N];
bool dd[N];
vector<int> ke[N];

ll hshdown[N], hshup[N], par[N], pw[N], dist[N];
unordered_map<ll, bool> S[N];
ll mxHigh = 0;

bool res = 0;

void calc_dfs (ll u, ll pa) {
    nChild[u] = 1;
    iter (&v, ke[u]) {
        if (v != pa && !dd[v]) {
            calc_dfs(v, u);
            nChild[u] += nChild[v];
        }
    }
}

ll get_cen (ll u, ll pa, ll sz_Tree) {
    iter (&v, ke[u]) {
        if (v != pa && !dd[v] && nChild[v] > sz_Tree / 2) {
            return get_cen(v, u, sz_Tree);
        }
    }
    return u;
}

void dfs1 (ll u, ll pa, ll centroid, ll Len) {
    dist[u] = dist[pa] + 1;
    mxHigh = max(mxHigh, dist[u]);
    if (dist[u] > Len || res)
        return;
    hshup[u] = (a[u] * pw[dist[u] - 2] % Mod + hshup[pa]) % Mod;
    hshdown[u] = (hshdown[pa] * bse % Mod + a[u]) % Mod;
    ll curHsh = (hshup[u] * pw[Len - dist[u] + 1] % Mod - hshdown[u] + Mod) % Mod;
    if (S[Len - dist[u] + 1].find(curHsh) != S[Len - dist[u] + 1].end()) {
        res = 1;
        return;
    }
    iter (&v, ke[u]) {
        if (v == pa || dd[v])
            continue;
        dfs1(v, u, centroid, Len);
    }
}

void dfs2 (ll u, ll pa, ll centroid, ll Len) {
    if (dist[u] > Len || res)
        return;
    ll curHsh = (hshup[u] * pw[Len - dist[u] + 1] % Mod - hshdown[u] + Mod) % Mod;
    S[dist[u]][curHsh] = 1;
    iter (&v, ke[u]) {
        if (v == pa || dd[v])
            continue;
        dfs2(v, u, centroid, Len);
    }
}

void decompose (ll u, ll Len) {
    if (res)
        return;
    calc_dfs(u, 0);
    ll centroid = get_cen(u, 0, nChild[u]);
    dd[centroid] = 1;

    mxHigh = 0;
    hshup[centroid] = 0;
    hshdown[centroid] = a[centroid];
    dist[centroid] = 1;
    ll curHsh = (hshup[centroid] * pw[Len] % Mod - hshdown[centroid] + Mod) % Mod;
    S[1][curHsh] = 1;
    iter (&v, ke[centroid]) {
        if (!dd[v]) {
            dfs1(v, centroid, centroid, Len);
            dfs2(v, centroid, centroid, Len);
        }
    }
    rep (i, 1, mxHigh) S[i].clear();
    iter (&v, ke[centroid]) {
        if (!dd[v]) {
            decompose(v, Len);
        }
    }
}

bool check (ll Len) {
    res = 0;
    rep (i, 1, n) {
        dd[i] = 0;
    }
    decompose(1, Len);
    return res;
}

ll BS (ll l, ll r) {
    while (l < r) {
        ll mid = l + r + 1 >> 1;
        if (check(mid * 2)) l = mid;
        else r = mid - 1;
    }
    return l * 2;
}

ll BS1 (ll l, ll r) {
    while (l < r) {
        ll mid = l + r + 1 >> 1;
        if (check(mid * 2 + 1)) l = mid;
        else r = mid - 1;
    }
    return l * 2 + 1;
}


void chloe_solution() {
    cin >> n;
    string s;
    cin >> s;
    rep (i, 1, n) {
        a[i] = s[i - 1] - '`';
    }
    rep (i, 2, n) {
        ll u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    pw[0] = 1;
    rep (i, 1, n) {
        pw[i] = (pw[i - 1] * bse) % Mod;
    }
    cout << max(BS(0, n / 2), BS1(0, (n - 1) / 2));
}

int main() {
//     file("lampice");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        chloe_solution();
}
/*
10
bcaabbbbac
2 1
3 1
4 1
5 2
6 5
7 2
8 5
9 4
10 8


*/

Compilation message

lampice.cpp: In function 'long long int BS(long long int, long long int)':
lampice.cpp:143:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  143 |         ll mid = l + r + 1 >> 1;
      |                  ~~~~~~^~~
lampice.cpp: In function 'long long int BS1(long long int, long long int)':
lampice.cpp:152:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |         ll mid = l + r + 1 >> 1;
      |                  ~~~~~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 6 ms 6748 KB Output is correct
3 Correct 19 ms 6912 KB Output is correct
4 Correct 23 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 13928 KB Output is correct
2 Correct 739 ms 14428 KB Output is correct
3 Correct 520 ms 14848 KB Output is correct
4 Correct 714 ms 15444 KB Output is correct
5 Correct 1041 ms 15640 KB Output is correct
6 Correct 90 ms 14852 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1581 ms 11512 KB Output is correct
2 Correct 1971 ms 11860 KB Output is correct
3 Correct 1675 ms 12324 KB Output is correct
4 Correct 1687 ms 11884 KB Output is correct
5 Correct 1236 ms 11268 KB Output is correct
6 Correct 1214 ms 11052 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 6 ms 6748 KB Output is correct
3 Correct 19 ms 6912 KB Output is correct
4 Correct 23 ms 6748 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 782 ms 13928 KB Output is correct
9 Correct 739 ms 14428 KB Output is correct
10 Correct 520 ms 14848 KB Output is correct
11 Correct 714 ms 15444 KB Output is correct
12 Correct 1041 ms 15640 KB Output is correct
13 Correct 90 ms 14852 KB Output is correct
14 Correct 1581 ms 11512 KB Output is correct
15 Correct 1971 ms 11860 KB Output is correct
16 Correct 1675 ms 12324 KB Output is correct
17 Correct 1687 ms 11884 KB Output is correct
18 Correct 1236 ms 11268 KB Output is correct
19 Correct 1214 ms 11052 KB Output is correct
20 Correct 1006 ms 9744 KB Output is correct
21 Correct 1120 ms 10504 KB Output is correct
22 Correct 1540 ms 10856 KB Output is correct
23 Correct 388 ms 9104 KB Output is correct
24 Correct 1366 ms 10668 KB Output is correct
25 Correct 1226 ms 10076 KB Output is correct
26 Correct 1651 ms 12124 KB Output is correct
27 Correct 1718 ms 11240 KB Output is correct
28 Correct 1137 ms 9180 KB Output is correct
29 Correct 1118 ms 9052 KB Output is correct
30 Correct 1273 ms 11404 KB Output is correct
31 Correct 1123 ms 10076 KB Output is correct
32 Correct 1006 ms 12396 KB Output is correct
33 Correct 795 ms 10836 KB Output is correct