제출 #1127391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127391		Zero_OP	Lampice (COCI19_lampice)	C++17	0 / 110	206 ms	20300 KiB

lampice

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define dbg(x) "[" #x " = " << (x) << "]"

const int MAX = 5e4 + 5;
const int base = 31;
const int mod = 1e9 + 9;

struct mint{
    int v;
    mint() : v(0) {}
    mint(int v) : v(v) {}
    mint& operator += (const mint& o){
        v += o.v;
        if(v >= mod) v -= mod;
        return *this;
    }

    mint& operator -= (const mint& o){
        v -= o.v;
        if(v < 0) v += mod;
        return *this;
    }

    mint& operator *= (const mint& o){
        v = 1ll * v * o.v % mod;
        return *this;
    }

    mint power(ll n) const{
        mint res(1), base = *this;
        for(; n > 0; n >>= 1, base *= base){
            if(n & 1) res *= base;
        }
        return res;
    }

    mint inv() const{
        return power(mod - 2);
    }

    mint& operator /= (const mint& o){ return *this *= o.inv(); }
    friend mint operator + (mint a, const mint& b){ return a += b; }
    friend mint operator - (mint a, const mint& b){ return a -= b; }
    friend mint operator * (mint a, const mint& b){ return a *= b; }
    friend mint operator / (mint a, const mint& b){ return a /= b; }
    friend bool operator == (const mint& a, const mint& b){ return a.v == b.v; }
    friend bool operator != (const mint& a, const mint& b){ return a.v != b.v; }
    friend ostream& operator << (ostream& out, const mint& v){ return out << v.v; }
};

mint base_power[MAX], inv_base_power[MAX];

int N, c[MAX];
vector<int> adj[MAX];
int sz[MAX], checking;
bool deleted[MAX], result;
vector<tuple<mint, mint, int>> subtree[MAX];

int dfs_sz(int u, int p){
    sz[u] = 1;
    for(auto v : adj[u]) if(v != p && !deleted[v]){
        sz[u] += dfs_sz(v, u);
    }
    return sz[u];
}

int find_centroid(int u, int p, int target){
    for(auto v : adj[u]) if(v != p && !deleted[v] && sz[v] * 2 > target){
        return find_centroid(v, u, target);
    }
    return u;
}

//the "hash" for string S (|S| = N) : h(S) = S[0] * base[N - 1] + S[1] * base[N - 2] + ... + S[N - 1]

void get_data(int u, int p, mint hash_c_to_u, mint hash_u_to_c, int dep, vector<tuple<mint, mint, int>>& receiver){
//    cout << u << ' ' << hash_c_to_u << ' ' << hash_u_to_c.v << ' ' << dep << '\n';
    receiver.emplace_back(hash_c_to_u, hash_u_to_c, dep);
    for(auto v : adj[u]) if(v != p && !deleted[v] && dep + 1 <= checking){
        mint hash_c_to_v = (hash_c_to_u * base) + c[v];
        mint hash_v_to_c = hash_u_to_c + (c[v] * base_power[dep]);
        get_data(v, u, hash_c_to_v, hash_v_to_c, dep + 1, receiver);
    }
}

int mx = 0;
set<int> S[MAX];

void insert(int i, mint v){
    //cout << "insert : " << i << ' ' << v << '\n';
    mx = max(mx, i);
    S[i].insert(v.v);
}

bool can(int i, mint v){
    //cout << "find : " << i << ' ' << v << '\n';
    return S[i].count(v.v);
}

void decompose(int u){
    u = find_centroid(u, -1, dfs_sz(u, -1));
    deleted[u] = true;

    mx = 0;
    for(auto v : adj[u]) if(!deleted[v]){
        subtree[v].clear();
        get_data(v, u, c[v], c[v], 1, subtree[v]);

        for(auto [hash_v_to_u, hash_u_to_v, len] : subtree[v]){
            mint hash_c_to_u = hash_v_to_u + c[u] * base_power[len];
            mint hash_u_to_c = (hash_u_to_v * base) + c[u];

            if(len + 1 == checking && hash_c_to_u == hash_u_to_c) {
                result = true;
                return;
            }
            mint target = (hash_u_to_c * base_power[checking - len - 1]) - hash_v_to_u;
            if(can(checking - len - 1, target)) {
                result = true;
                return;
            }
        }

        for(auto [hash_v_to_u, hash_u_to_v, len] : subtree[v]){
            mint hash_u_to_c = (hash_u_to_v * base) + c[u];
            mint target = (hash_u_to_c * base_power[checking - len - 1]) - hash_v_to_u;
            insert(len, target);
        }

        subtree[v].clear();
    }

    for(int i = 0; i <= mx; ++i){
        S[i].clear();
    }

    for(auto v : adj[u]) if(!deleted[v]){
        decompose(v);
        if(result) return;
    }
}

bool check(int x){
    checking = x;
    for(int i = 0; i <= N; ++i){
        sz[i] = 0;
        deleted[i] = 0;
        S[i].clear();
        subtree[i].clear();
    }

    result = false;
    decompose(1);
    return result;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); srand(time(nullptr));

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    cin >> N;
    for(int i = 1; i <= N; ++i){
        char ch; cin >> ch;
        c[i] = ch - 'a' + 1;
    }

    base_power[0] = 1; inv_base_power[0] = 1;
    for(int i = 1; i <= N; ++i) base_power[i] = base_power[i - 1] * base;

    inv_base_power[N] = base_power[N].inv();
    for(int i = N - 1; i >= 1; --i){
        inv_base_power[i] = inv_base_power[i + 1] * base;
    }

    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;

    //odd -> 2l + 1
    int lo = 1, hi = (N - 1) / 2;
    while(lo <= hi){
        int mid = lo + hi >> 1;
        if(check(2 * mid + 1)) ans = max(ans, 2 * mid + 1), lo = mid + 1;
        else hi = mid - 1;
    }

    lo = 1, hi = N / 2;
    while(lo <= hi){
        int mid = lo + hi >> 1;
        if(check(2 * mid)) ans = max(ans, 2 * mid), lo = mid + 1;
        else hi = mid - 1;
    }

    cout << ans << '\n';

    return 0;
}

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