Submission #501007

#	Time	Username	Problem	Language	Result	Execution time	Memory
501007		Duy_e	Lampice (COCI19_lampice)	C++14	110 / 110	3821 ms	30752 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;
}

ll get(int u, int v) {return (H[v] - H[u] * pw[h[v] - h[u]] + MOD * MOD) % MOD;}

bool solve_len(int len, int u) {
    // return true;

    if (len <= 1) return true;
    H[u] = s[u]; rH[u] = s[u]; h[u] = 0;
    dfs(u, u, 0);

    unordered_set <int> st, st2; st.insert(0); st2.insert(0);

    // cout << "--------- " << u << " ----------\n";
    for (int vi: d[u]) if (!dead[vi]) {
        for (int v: save[vi]) {
            // cout << v << ' ';
            int mis = len - h[v] - 1; if (mis < 0) continue;
            // cout << u << ' ' << v << ' ' << get(u, v) << '\n';
            if (mis >= h[v]) {
                if (st2.count(get(u, v))) return true;
            } else {
                int anc = kanc(mis, v);
                if (H[anc] == rH[anc] && st.count(get(anc, v))) return true;
            }
        }
        // cout << '\n';
        for (int v: save[vi]) {
            int mis = len - h[v] - 1; if (mis < 0) continue;
            if (mis > h[v]) st.insert(get(u, v)); else  {
                int anc = kanc(mis, v);
                if (H[anc] == rH[anc]) st2.insert(get(anc, v));
            }
        }
    }

    return false;
}


int solve(int len) {
    for (int i = 1; i <= n; i ++) dead[i] = false;
    for (int u: centroid) {
        int tmp = solve_len(len, u);
        dead[u] = true;
        for (int v: d[u]) save[v].clear();
        if (tmp) return true;
    }

    return false;
}

int bs(int x) {
    int l = 0, r = n/2 + 1, ans = x;
    while (l <= r) {
        int mid = l + r >> 1;
        // cout << mid*2 + x << '\n';
        if (solve(2*mid + x))
            ans = mid * 2 + x, l = mid + 1;
        else
            r = mid - 1;
    }

    return ans;
}

ll SOLVE_CENTROID() {   
    return max(bs(0), bs(1));
}   

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // #ifndef ONLINE_JUDGE
    //     freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
    // #endif
    
    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();// << ' ' << 1;
    return 0;
}    
/**  /\_/\
    (= ._.)
    / >🍵 \>🍮
  ________________________
 / Brainstorming section /
/=======================/
---
===
g++ -O2 -std=c++11 -Wall -Wl,--stack=268435456 somerandomthings.cpp -o somerandomthings.exe
12780

===
**/
// 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)':
lampice.cpp:134:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  134 |         int mid = l + r >> 1;
      |                   ~~^~~

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