제출 #1156695

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156695		knhatdev	Lampice (COCI19_lampice)	C++17	110 / 110	2591 ms	13844 KiB

lampice

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

const int N = 5e4 + 5, base = 311, mod = 1e9 + 7;
int n, sz[N], h[N], ans;
int up[N], down[N], H, mx_h;
int Pow[N], a[N];
bool is_centroid[N];
string s;
vector<int> g[N];
map<int, bool> d[N];

void dfs(int u, int par){
    sz[u] = 1;
    for(int v : g[u]){
        if(v == par || is_centroid[v]) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int find_centroid(int u, int tree_sz, int par){
    for(int v : g[u]){
        if(v != par && !is_centroid[v] && sz[v] > tree_sz/2)
            return find_centroid(v, tree_sz, u);
    }
    return u;
}  

bool get(int u, int par){
    h[u] = h[par] + 1;
    if(h[u] > H) return 0;
    mx_h = max(mx_h, h[u]);
    down[h[u]] = (down[h[u] - 1]*base + a[u]) % mod;
    up[h[u]] = (a[u] * Pow[h[u] - 1] + up[h[u] - 1]) % mod;
    int tmp = (up[h[u]] * Pow[H - h[u]] - down[h[u]] + mod) % mod;
    if(up[h[u]] == down[h[u]] && h[u] == H) return 1;
    if (d[H - h[u]].find(tmp) != d[H - h[u]].end()) return 1;
    for(int v : g[u]){
        if(v != par && !is_centroid[v])
            if(get(v, u)) return 1;
    }
    return 0;
}


void update(int u, int par){
    h[u] = h[par] + 1;
    if(h[u] > H) return;
    mx_h = max(mx_h, h[u]);
    down[h[u]] = (down[h[u] - 1]*base + a[u]) % mod;
    up[h[u]] = (a[u] * Pow[h[u] - 1] + up[h[u] - 1]) % mod;
    int tmp = (up[h[u]] * Pow[H - h[u]] - down[h[u]] + mod) % mod;
    d[h[u]][tmp] = 1;
    for(int v : g[u])  
        if(v != par && !is_centroid[v])
            update(v, u);
}

bool build_centroid(int u){
    dfs(u, -1);
    int centroid = find_centroid(u, sz[u], -1);
    is_centroid[centroid] = 1;
    mx_h = 0;
    for(int v : g[centroid]){
        if(!is_centroid[v]){
            h[centroid] = 1;
            up[1] = down[1] = a[centroid];
            if(get(v, centroid)) return 1;
            h[centroid] = up[0] = down[0] = 0;
            update(v, centroid);
        }
    }
    for(int i = 0; i <= mx_h; i++)
        d[i].clear();
    for(int v : g[centroid])
        if(!is_centroid[v]) 
            if(build_centroid(v))
                return 1;

    return 0;
}

bool check(int x){
    if(x > n) return 0;
    for(int i = 1; i <= n; i++){
        d[i].clear();
        is_centroid[i] = 0;
    }
    H = x;
    return build_centroid(1);
}
void solve(){
    int l = 1, r = n;
    ans = 1;
    while(l <= r){
        int mid = (l + r)/2;
        if(check(mid * 2)){
            l = mid + 1;
            ans = max(ans, mid * 2);
        } else {
            r = mid - 1;
        }
    }
    l = 1, r = n;
    while(l <= r){
        int mid = (l + r)/2;
        if(check(mid*2 + 1)){
            l = mid + 1;
            ans = max(ans, mid * 2 + 1);
        } else {
            r = mid - 1;
        }
    }
    cout << ans;
}
main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> s;
    s = ' ' + s;
    for(int i = 1; i <= n; i++)
        a[i] = s[i] - 'a' + 1;
    // for(int i = 1; i <= n; i++)
    //     cout << a[i] << ' ';
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    Pow[0] = 1;
    for(int i = 1; i <= n; i++){
        Pow[i] = (Pow[i - 1] * base) % mod;
    }
    solve();
}

컴파일 시 표준 에러 (stderr) 메시지

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

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