Submission #1281914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281914		LmaoLmao	Lampice (COCI19_lampice)	C++20	110 / 110	4188 ms	15316 KiB

lampice

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,10>;

const int N = 2e5+5;
const int INF = 1e9;
const int base=311;
const int MOD=1e9+7;

int binpow(int a,int b) {
    int res=1;
    while(b>0) {
        if(b & 1) res=res * a % MOD;
        a=a*a% MOD;
        b/=2;     
    }
    return res; 
}

int n;
int del[100005];
vector<int> adj[100005];
int s[100005];
int a[200005];
map<int,int> mp[100005];
int res,mid,lmao;

int dfs(int u,int p) {
    s[u]=1;
    for(int v:adj[u]) {
        if(del[v] || v==p) continue;
        s[u]+=dfs(v,u);
    }
    return s[u];
} 
int centroid(int u,int p,int tsz) {
    for(int v:adj[u]) {
        if(del[v] || v==p) continue; 
        if(s[v]*2>tsz) return centroid(v,u,tsz);
    }
    return u;
}
void get(int u,int p,int cur,int val1,int val2,int type) {
    if(cur>mid-type) return;
    int tmp=(val1-(val2*binpow(base,mid-cur)%MOD)+MOD)%MOD;
    if(!type) {
        res|=mp[mid-cur].count(tmp);
    } 
    else {
        lmao=max(lmao,cur);
        mp[cur][tmp]=1;
    }
    //cout << u<< ' '  << cur << ' ' << tmp << ' ' << val1 << ' ' << val2 << ' ' << res << ' ' << type << endl;
    for(int v:adj[u]) {
        if(del[v] || v==p) continue;
        get(v,u,cur+1,(val1*base+a[v])%MOD,(val2+a[v]*binpow(base,cur))%MOD,type);
    }
}
void build(int u) {
    int cen=centroid(u,-1,dfs(u,-1));
    del[cen]=1;
    lmao=0;
    mp[0][0]=1;
    for(int v:adj[cen]) {
        if(del[v]) continue;
        get(v,cen,2,a[cen]*base+a[v],a[v]*base+a[cen],0);
        get(v,cen,1,a[v],a[v],1);
    }
    for(int i=1;i<=lmao;i++) {
        mp[i].clear();
    }
    //cout << cen << ' ' << lmao << ' ' << mp[1][999806567] << endl;
    //return;
    for(int v:adj[cen]) {
        if(del[v]) continue;
        build(v);
        if(res) return;
    }
}

bool check() {
    res=0;
    for(int i=1;i<=n;i++) del[i]=0;
    build(1);
    return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++) {
        char x; cin >> x;
        a[i]=(x-'a')+1;
    }
    for(int i=1;i<n;i++) {
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int ans=1,l=1,r=n/2;
    while(l<=r) {
        mid=(l+r)/2;
        mid*=2;
        if(check()) {
            ans=mid;
            l=mid/2+1;
        }
        else r=mid/2-1;
    }
    l=ans/2+1,r=(n+1)/2;
    while(l<=r) {
        mid=(l+r)/2;
        mid=mid*2-1;
        //cout << mid << endl;
        if(check()) {
            ans=max(ans,mid);
            l=(mid+1)/2+1;
        }
        else r=(mid+1)/2-1;
    }
    cout << ans;
    return 0;
}
/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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