Submission #1103815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103815		YugiHacker	Lampice (COCI19_lampice)	C++17	0 / 110	1094 ms	21540 KiB

lampice

/*
	www.youtube.com/YugiHackerChannel
	linktr.ee/YugiHacker
*/
#include<bits/stdc++.h>
#define el cout<<"\n"
#define f0(i,n) for(int i=0;i<n;++i)
#define f1(i,n) for(int i=1;i<=n;++i)
#define maxn 50004
#define base 31
#define MOD 1000000007
using namespace std;
int n;
long long pw[maxn];
string s;
vector <int> a[maxn];
int sz[maxn], del[maxn];
void dfs_sz(int u, int p=-1) {
    sz[u] = 1;
    for (int v:a[u]) if (v != p && !del[v]) dfs_sz(v, u), sz[u] += sz[v];
}
int get_centroid(int u, int p, int n) {
    for (int v:a[u]) if (v != p && !del[v] && sz[v] * 2 > n) return get_centroid(v, u, n);
    return u;
}

int ma;
map <long long, int> mp[maxn];

bool dfs(int u, int p, int h, int len, long long H_up, long long H_down, bool update) {
    if (h > len) return 0;
    ma = max(ma, h);
    H_up = (H_up + (s[u] - 'a' + 1) * pw[h-1]) % MOD;
    H_down = (H_down * base + s[u] - 'a' + 1) % MOD;
    long long H = (H_up * pw[len - h] - H_down + MOD) % MOD;
    if (update) mp[h][H] = 1;
    else {
        if (mp[len - h - 1].count(H)) return 1;
    }
    for (int v:a[u]) if (v != p && !del[v])
        if (dfs(v, u, h+1, len, H_up, H_down, update)) return 1;
    return 0;
}

bool CentroidDecomposition(int u, int len) {
    dfs_sz(u);
    u = get_centroid(u, -1, sz[u]);
    del[u] = 1;
    long long H_down = s[u] - 'a' + 1;
    long long H_up = 0;
    long long H = (H_up * pw[len] - H_down + MOD) % MOD;
    mp[0][H] = 1;
    for (int v:a[u]) if (!del[v])
    {
        if (dfs(v, u, 1, len, H_up, H_down, 0)) return 1;
        dfs(v, u, 1, len, H_up, H_down, 1);
    }
    f0 (i, ma + 1) mp[i].clear();
    for (int v:a[u]) if (!del[v]) if (CentroidDecomposition(v, len)) return 1;
    return 0;
}

bool check (int len) {
    f1 (u, n) del[u] = 0;
    f0 (i, ma + 1) mp[i].clear();
    return CentroidDecomposition(1, len);
}

main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> s;
    pw[0] = 1;
    for (int i=1; i<=n; i++) pw[i] = pw[i-1] * base % MOD;
    s = ' ' + s;
    f1 (i, n-1) {
        int u, v; cin >> u >> v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int ans = 1;
    int l = 0, r = n/2+1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (check(m*2)) l = m;
        else r = m;
    }
    ans = max(ans, l * 2);
    l = 0, r = n/2+1;
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (check(m*2+1)) l = m;
        else r = m;
    }
    ans = max(ans, l * 2 + 1);
    cout << ans;
}

Compilation message (stderr)

lampice.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main()
      | ^~~~

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