oj.uz

Submission #1022127

# Submission time Handle Problem Language Result Execution time Memory
1022127 2024-07-13T10:21:41 Z _shr104 Lampice (COCI19_lampice) C++14
17 / 110
 5000 ms 10168 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 31 ms 1624 KB Output is correct
4 Correct 22 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1436 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5049 ms 10168 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5029 ms 8108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 6 ms 1628 KB Output is correct
3 Correct 31 ms 1624 KB Output is correct
4 Correct 22 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1436 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Execution timed out 5049 ms 10168 KB Time limit exceeded
9 Halted 0 ms 0 KB -