Submission #1022127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022127		_shr104	Lampice (COCI19_lampice)	C++14	17 / 110	5049 ms	10168 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+11, mxn = 5e4+7;
string s;
ll sz[mxn], n, pw[mxn], up[mxn], dn[mxn], d[mxn];
bool del[mxn], ck;
vector<vector<ll>> g(mxn);
struct h_f {ll operator() (const pair<ll,ll>& x) const {return x.fi^x.se;}};
unordered_set<pair<ll,ll>,h_f> mp;
void dfs_sz(ll u, ll v) {sz[u] = 1; for (ll i : g[u]) {if (i != v && !del[i]) {dfs_sz(i,u); sz[u] += sz[i];}}}
ll dfs_ctr(ll u, ll v, ll szx) {for (ll i : g[u]) {if (i != v && !del[i] && sz[i] > szx/2) {return dfs_ctr(i,u,szx);}} return u;}
ll vv(ll x) {return s[x]-'a'+1;}
void cal(ll u, ll v)
{
    for (ll i : g[u])
    {
        if (i != v && !del[i])
        {
            d[i] = d[u]+1;
            up[i] = (up[u]+(long long)vv(i)*pw[d[i]])%mod;
            dn[i] = ((long long)dn[u]*31+vv(i))%mod;
            cal(i,u);
        }
    }
}
void upd_ans(ll u, ll v, ll cr, ll root)
{
    if (ck) return;
    if (d[u] == cr) if (((long long)up[u]+vv(root))%mod == dn[u]) 
    {
        // cerr << "SINGLE ROAD: " << u << '\n';
        ck = 1;
    }
    // cerr << "CHECKED VALUE: " << u << ' ' << d[u] << ' ' << ((up[u]*pw[cr-d[u]]-dn[u])%mod+mod)%mod << '\n';
    if (mp.count({d[u],(((long long)up[u]*pw[cr-d[u]]-dn[u])%mod+mod)%mod})) ck = 1;
    if (ck) return;
    for (ll i : g[u]) {if (i != v && !del[i]) {upd_ans(i, u, cr, root);}}
}
void add(ll u, ll v, ll cr)
{
    if (ck) return;
    if (d[u] < cr) 
    {
        // cerr << "ADDED VALUE: " << u << ' ' << cr-d[u] << ' ' << ((up[u]*pw[cr-d[u]]-dn[u])%mod+mod)%mod << '\n';
        mp.insert({cr-d[u],(((long long)up[u]*pw[cr-d[u]]-dn[u])%mod+mod)%mod});
    }
    for (ll i : g[u]) {if (i != v && !del[i]) {add(i, u, cr);}}
}
void upd(ll u, ll cr) 
{
    // cerr << "CENTROID: " << u << '\n';
    if (ck) return;
    d[u] = up[u] = 0; dn[u] = vv(u); cal(u,u); mp.clear();
    for (ll i : g[u])
    {
        if (!del[i])
        {
            upd_ans(i,u,cr,u);
            add(i,u,cr);
        }
    }
    mp.clear();
}
void solve(ll u, ll cr)
{
    dfs_sz(u,u); ll n_root = dfs_ctr(u,u,sz[u]);
    upd(n_root, cr); del[n_root] = 1;
    if (ck) return;
    for (ll i : g[n_root]) {if (!del[i]) solve(i, cr);}
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
    cin >> n >> s; s = '#' + s; pw[0] = 1;
    for (ll i = 1; i <= n; i++) pw[i] = ((long long)pw[i-1]*31)%mod;
    for (ll i = 1; i < n; i++)
    {
        ll a, b; cin >> a >> b;
        g[a].pb(b); g[b].pb(a);
    }
    ll l = 0, r = n; ll ans = 0;
    while (r >= l)
    {
        ll m = (r+l)>>1;
        ck = 0; mp.clear();
        for (ll i = 1; i <= n; i++) del[i] = 0; 
        // cerr << "CURRENT LENGTH: " << m << '\n' << '\n';
        solve(1,m);
        // cerr << '\n';
        if (ck) {ans = m; l = m+1;}
        else 
        {
            ck = 0; mp.clear();
            for (ll i = 1; i <= n; i++) del[i] = 0; 
            // cerr << "CURRENT LENGTH: " << m+1 << '\n' << '\n';
            solve(1,m+1);
            // cerr << '\n';
            if (ck) {ans = m; l = m+1;}
            else r = m-1;
        }
    }
    ck = 0; mp.clear();
    for (ll i = 1; i <= n; i++) del[i] = 0; 
    solve(1,ans+1);
    if (ck) cout << ans+2;
    else cout << ans+1;
}

• Subtask 1: 17 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37