Submission #1283090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283090		dhuyyyy	Lampice (COCI19_lampice)	C++20	110 / 110	4967 ms	12544 KiB

lampice

#include<bits/stdc++.h>
#define fi first
#define se second

using namespace std;

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

const int N = 50005;
const ll INF = 1e18;
const ll MOD = 1e9+7;
const int base = 311;

int n, u, v, root, mid, mx = 0, ans = 1;

ll x, y;

//hashing
ll a[N];

//centroid
int sz[N];
bool num[N];

// tree
char c;
vector <int> adj[N];

//answer
bool ok;
map<ll,bool> mp[N];
int getSize(int u,int p){
    sz[u] = 1;
    for (int it : adj[u]){
        if (it == p || num[it]) continue;
        sz[u] += getSize(it,u);
    }
    return sz[u];
}
int getCentroid(int u,int p,int n){
    for (int it : adj[u]){
        if (it == p || num[it]) continue;
        if (sz[it] * 2 > n) return getCentroid(it,u,n);
    }
    return u;
}
ll binpow(ll a,ll b){
    ll res = 1;
    while (b > 0){
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
void dfs(int u,int p,ll xuoi,ll nguoc,int type,int depth){
    if (depth > mid - type) return;
    /*
    x1 + y2 * base |x1| = x2 + y1 * base |x2|
    x1 - y1 * base ^ (mid - |x1|) = x2 - y2 * base ^ |x1|
    |x1| ở đây là depth
    */
    ll val = (xuoi - (nguoc * binpow(base,mid - depth) % MOD) + MOD) % MOD;
    if (!type){
        if (mp[mid - depth].count(val) > 0){
            ok = 1;
            return;
        }
    } else{
        mx = max(mx,depth);
        mp[depth][val] = 1;
    }
    for (int it : adj[u]){
        if (it == p || num[it]) continue;
        x = (xuoi * base + a[it]) % MOD;
        y = (nguoc + a[it] * binpow(base,depth)) % MOD;
        dfs(it,u,x,y,type,depth + 1);
    }
}
void decompose(int u){
    root = getCentroid(u,0,getSize(u,0));
    num[root] = 1;
    mx = 0;
    mp[0][0] = 1;
    for (int it : adj[root]){
        if (num[it]) continue;
        dfs(it,root,a[root] * base + a[it],a[it] * base + a[root],0,2);
        if (ok){
            for (int i = 1; i <= mx; i++){
                mp[i].clear();
            }
            return;
        }
        dfs(it,root,a[it],a[it],1,1);
    }
    for (int i = 1; i <= mx; i++){
        mp[i].clear();
    }
    for (int it : adj[root]){
        if (num[it]) continue;
        decompose(it);
    }
}
bool check(){
    ok = 0;
    for (int i = 1; i <= n; i++) num[i] = 0;
    decompose(1);
    return ok;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> c;
        a[i] = (c - 'a' + 1);
    }
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int l = 1, r = n / 2;
    while (l <= r){
        mid = (l + r) >> 1;
        mid <<= 1;
        if (check()){
            ans = mid;
            l = (mid >> 1) + 1;
        } else r = (mid >> 1) - 1;
    }
    l = ans / 2 + 1, r = (n + 1) / 2;
    while (l <= r){
        mid = (l + r) >> 1;
        mid = (mid << 1) - 1;
        if (check()){
            ans = max(ans,mid);
            l = ((mid + 1) >> 1) + 1;
        } else r = ((mid + 1) >> 1) - 1;

    }
    cout << ans;
    return 0;
}

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