Submission #500920

#	Time	Username	Problem	Language	Result	Execution time	Memory
500920		Duy_e	Lampice (COCI19_lampice)	C++14	48 / 110	2289 ms	26768 KiB

lampice

#include <bits/stdc++.h>
#define debug cout << "fuck\n";
#define ll long long
#define ull unsigned long long
#define pii pair<long long, long long>
#define st first
#define nd second
#define file "test"
using namespace std;
const long long oo = 1e18;
const long long N = 2e5 + 5;
const long long base = 311;
const long long MOD = 2e9 + 7;

ll H[N], rH[N], pw[N], h[N], up[20][N];

vector <int> d[N], centroid;
string SS;

int n, numchild[N], s[N];
bool dead[N];

// find centroid
int get_size(int p, int u) {
    int ans = 1;
    for (int v: d[u]) if (v != p && !dead[v]) 
        ans += get_size(u, v);
    return ans;
}

int find_centroid(int S, int p, int u, int ma = 0) {
    numchild[u] = 1;
    for (int v: d[u]) if (v != p && !dead[v]) {
        int get = find_centroid(S, u, v);

        if (get != -1) return get;

        numchild[u] += numchild[v];
        ma = max(ma, numchild[v]);
    }

    ma = max(ma, S - numchild[u]);

    return ma <= S/2 ? u: -1;
}

void FIND_CENTROID() { 
    queue <int> q; q.push(1);
    while (q.size()) {
        int u = q.front(); q.pop();
        dead[u = find_centroid(get_size(0, u), 0, u)] = true;
        centroid.push_back(u); 
        for (int v: d[u]) if (!dead[v]) q.push(v); 
    }
}

vector <int> save[N];

void dfs(int p, int u, int vi) {
    for (int v: d[u]) if (v != p && !dead[v]) {
        h[v] = h[u] + 1;
        H[v] = (H[u]*base + s[v]) % MOD;
        rH[v] = (rH[u] + pw[h[v]]*s[v]) % MOD;

        up[0][v] = u;
        for (int i = 1; (1 << i) <= h[v]; i ++)
            up[i][v] = up[i - 1][up[i - 1][v]];

        save[vi == 0 ? v : vi].push_back(v);
        dfs(u, v, vi == 0 ? v : vi);
    }
}   

int kanc(int k, int u) {
    int x = u;
    for (int i = 19; i >= 0; i --) 
        if (k & 1 << i) u = up[i][u];
    return u;
}

bool solve_len(int len, int u) {
    // return true;
    if (len <= 1) return true;
    set <int> st, st2;
    for (int vi: d[u]) if (!dead[vi]) {
        for (int v: save[vi]) {
                if (h[v] >= len) continue;            

            
            int mis = len - h[v] - 1;
            if (st2.count((H[v] - H[u]*pw[h[v] - h[u]] + MOD * MOD) % MOD))
                return true;

            if (mis < 0) continue;

            if (mis > h[v]) continue;
            if (mis == 0) {
                if (H[v] == rH[v]) return true;
                continue;
            }

            int anc = kanc(mis - 1, v), anc2 = up[0][anc];
           
            if (H[anc2] == rH[anc2]) {
                ll get = (H[v] - H[anc2]*pw[h[v] - h[anc2]] + MOD * MOD) % MOD;
                if (st.count(get)) return true;
            }
        
        }

        for (int v: save[vi]) { 
            if (h[v] >= len) continue;
            st.insert((H[v] - H[u]*pw[h[v] - h[u]] + MOD * MOD) % MOD);

            {
                int mis = len - h[v] - 1;
                if (mis < 0) continue;
                if (mis > h[v]) continue;
                if (mis == 0) continue;
                int anc = kanc(mis - 1, v), anc2 = up[0][anc];

                if (H[anc2] == rH[anc2]) {
                    ll get = (H[v] - H[anc2]*pw[h[v] - h[anc2]] + MOD * MOD) % MOD;
                    st2.insert(get);
                }
            }
        }
    }

    return false;
}

int bs(int x, int u) {
    int l = 0, r = n, ans = x;
    while (l <= r) {
        int mid = l + r >> 1;
        if (solve_len(mid * 2 + x, u))
            ans = mid * 2 + x, l = mid + 1;
        else
            r = mid - 1;
    }

    return ans;
}

int solve(int u) {
    H[u] = s[u]; rH[u] = s[u]; h[u] = 0;
    dfs(u, u, 0);
    ll ans = max(bs(1, u), bs(0, u));
    for (int v: d[u]) save[v].clear();
    return ans;
}

ll SOLVE_CENTROID() {
    memset(dead, false, sizeof dead);
    int ans = 0;
    for (int u: centroid) {
        dead[u] = true;
        ans = max(ans, solve(u));
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> SS;
    // s = ' ' + s;

    for (int i = 1; i <= n; i ++)
        s[i] = SS[i - 1] - 'a' + 1;

    pw[0] = 1;
    for (int i = 1; i < N; i ++) 
        pw[i] = pw[i - 1]*base % MOD;

    for (int i = 1, u, v; i < n; i ++) {
        cin >> u >> v;
        d[u].push_back(v);
        d[v].push_back(u);
    }

    FIND_CENTROID();
    cout << SOLVE_CENTROID();
    return 0;
}    
/**  /\_/\
    (= ._.)
    / >🍵 \>🍮
  ________________________
 / Brainstorming section /
/=======================/
---
===


===
**/
// Before submit: spot the visible bug by reading the code. 

Compilation message (stderr)

lampice.cpp: In function 'int kanc(int, int)':
lampice.cpp:75:9: warning: unused variable 'x' [-Wunused-variable]
   75 |     int x = u;
      |         ^
lampice.cpp: In function 'int bs(int, int)':
lampice.cpp:136:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  136 |         int mid = l + r >> 1;
      |                   ~~^~~

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