제출 #1283066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283066		dhuyyyy	Lampice (COCI19_lampice)	C++20	0 / 110	3974 ms	100796 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<int, int>;
using aa = array<int,4>;

const int N = 1e5+5;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int base = 31;

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

bool ok;
//hashing
int po[N], a[N];

//centroid
int sz[N];
bool num[N];
vector <aa> anc[N];

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

//answer
map<int,bool> mp[N];
void getSize(int u,int p){
    sz[u] = 1;
    for (int it : adj[u]){
        if (it == p || num[it]) continue;
        getSize(it,u);
        sz[u] += sz[it];
    }
}
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;
}
void dfs(int u,int p,int cur,int depth,int type){
    if (depth > (mid + 1) / 2) return;
    if (!type){
        if (mp[mid / 2][cur] == 1){
            ok = 1;
        }
    } else{
        mx = max(mx,depth);
        mp[depth][cur] = 1;
    }
    if (ok) return;
    for (int it : adj[u]){
        if (it == p || num[it]) continue;
        if (mid & 1) dfs(it,u,(cur * po[depth + 1] + a[it]) % MOD,depth + 1,type);
        else{
            if (type) dfs(it,u,(cur * po[depth + 1] + a[it]) % MOD,depth + 1,1);
            else dfs(it,u,(cur * po[depth + 2] + a[it]) % MOD,depth + 1,0);
        }
    }
}
void decompose(int u){
    getSize(u,0);
    int m = sz[u];
    root = getCentroid(u,0,m);
    num[root] = 1;
    mx = 0;
    mp[0][0] = 1;
    for (int it : adj[root]){
        if (num[it]) continue;
        if (mid % 2 == 0){
            // mid chan
            dfs(it,root,a[root] * po[2] + a[it],1,0);
        } else{
            dfs(it,root,a[it],1,0);
        }
        dfs(it,root,a[it],1,1);
    }
    //cout << root << '\n';
    for (int i = 1; i <= mx; i++){
        mp[i].clear();
    }
    if (ok) return;
    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);cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> c;
        a[i] = (c - 'a' + 1);
    }
    ans = 1;
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        if (a[u] == a[v]) ans = 2;
    }
    po[0] = 1;
    for (int i = 1; i <= n; i++){
        po[i] = po[i-1] * base % MOD;
    }
    int l = 1, r = n / 2;
    while (l <= r){
        mid = (l + r) >> 1;
        mid *= 2;
        if (check()){
            ans = max(ans,mid);
            l = mid / 2 + 1;
        } else r = mid / 2 - 1;
    }
    l = 1, r = n / 2;
    while (l <= r){
        mid = (l + r) >> 1;
        mid = mid * 2 - 1;
        if (check()){
            ans = max(ans,mid);
            l = (mid + 1) / 2 + 1;
        } else r = (mid + 1) / 2 - 1;
    }
    cout << ans;
    return 0;
}

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