Submission #1126251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126251		whoknow	Lampice (COCI19_lampice)	C++20	110 / 110	2843 ms	13056 KiB

lampice

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN 50005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const int mod = 1e9 + 7, BASE = 31;
int n;
int a[MAXN];
vector<int>g[MAXN];
namespace sub1
{
bool ans ;
int sz[MAXN], h[MAXN];
int P[MAXN], up[MAXN], down[MAXN];
bool del[MAXN];
map<ll, bool>cnt[MAXN];
int dem(int u, int p)
{
    int cnt = 1;
    for(int v : g[u])
        if(v != p && !del[v])
            cnt += dem(v, u);
    return sz[u] = cnt;
}
int centroid(int u, int p, int size)
{
    for(int v : g[u])
        if(v != p && !del[v] && sz[v] > size / 2)
            return centroid(v, u, size);
    return u;
}
void calc(int u, int p, int len)
{
    h[u] = h[p] + 1;
    if(h[u] > len||ans)
        return ;
    down[u] = (1LL * down[p] * BASE % mod + a[u]) % mod;
    up[u] = (1LL * a[u] * P[h[u] - 2] % mod + up[p]) % mod;
    ll need = (1LL * up[u] * P[len - (h[u] - 1)] % mod - down[u] + mod) % mod;
    if(cnt[len - h[u] + 1].find(need) != cnt[len - h[u] + 1].end())
        return ans = 1, void();
    for(int v : g[u])
        if(v != p && !del[v])
            calc(v, u, len);
}
void add(int u, int p, int len)
{
    if(h[u] > len||ans)
        return ;
    ll bu = (1LL * up[u] * P[len - h[u] + 1] % mod - down[u] + mod) % mod;
    cnt[h[u]][bu] = 1;
    for(int v : g[u])
        if(v != p && !del[v])
            add(v, u, len);
}
void dfs(int u, int len)
{
    if(ans)
        return ;
    int size = dem(u, 0);
    u = centroid(u, 0, size);
    up[u] = 0;
    down[u] = a[u];
    h[u] = del[u] = 1;
    cnt[1][(1LL * up[u]*P[len] % mod - down[u] + mod) % mod] = 1;
    for(int v : g[u])
        if(!del[v])
        {
            calc(v, u, len);
            add(v, u, len);
        }
    for(int i = 1; i <= size; i++)
        cnt[i].clear();
    for(int v : g[u])
        if(!del[v])
            dfs(v, len);
}
bool check(int D)
{
    ans = 0;
    for(int i = 1; i <= n; i++)
        del[i] = 0;
    dfs(1, D);
    return ans;
}
int bina(int l, int r, int p)
{
    while(l < r)
    {
        int mid = (l + r + 1) / 2;
        if(check(mid * 2 + p))
            l = mid;
        else
            r = mid - 1;
    }
    return l * 2 + p;
}
void solve()
{
    P[0] = 1;
    for(int i = 1; i <= n; i++)
        P[i] = 1LL * P[i - 1] * BASE % mod;
    cout << max(bina(0, n / 2, 0), bina(0, (n - 1) / 2, 1));
}
}
main()
{
    if(fopen("TEST.inp", "r"))
    {
        freopen("TEST.inp", "r", stdin);
        freopen("TEST.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> n >> s;
    for(int i = 1; i <= n; i++)
        a[i] = s[i - 1] - 'a' + 1;
    for(int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    sub1::solve();
}

Compilation message (stderr)

lampice.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main()
      | ^~~~
lampice.cpp: In function 'int main()':
lampice.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("TEST.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen("TEST.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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