Submission #1287717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287717		khoile08	Lampice (COCI19_lampice)	C++20	110 / 110	4452 ms	63792 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define ll long long
#define db double
#define ii pair<int,int>
#define pb push_back
#define MASK(i) (1LL << i)
#define sq(i) (1LL * (i) * (i))
#define task "khoile08"
#define pow khoile

const ll INF = 1e18;
const int inf = 1e9;
const int N = 5e4 + 2;
const int mod = 998244353;
const int base = 311;

int add(int a, int b) {
    a += b;
    if(a < 0) a += mod;
    if(a >= mod) a -= mod;
    return a;
}

int mul(int a, int b) {
    return 1LL * a * b % mod;
}

int n;
vector<int> g[N];
char c[N];
int pow[N];

int sze[N];
bool del[N];
unordered_map<int,bool> check[N];

void calsize(int u, int p) {
    sze[u] = 1;
    for(int v : g[u]) {
        if(v == p || del[v]) continue;
        calsize(v, u);
        sze[u] += sze[v];
    }
}

int findcen(int u, int p, int s) {
    for(int v : g[u]) {
        if(v == p || del[v] || sze[v] <= s / 2) continue;
        return findcen(v, u, s);
    }
    return u;
}

bool cal(int u, int p, int hu, int hd, int h, int k, int &maxdepth) {
    if(h > k) return false;
    maxdepth = max(maxdepth, h);

    hu = add(hu, mul(c[u], pow[h - 1]));
    if(p != -1) hd = add(mul(hd, base), c[u]);

    int tar = add(mul(hu, pow[k - h]), -hd);
    if(check[k - h + 1][tar]) return true;

    for(int v : g[u]) {
        if(v == p || del[v]) continue;
        if(cal(v, u, hu, hd, h + 1, k, maxdepth)) return true;
    } 
    return false;
}

void mark(int u, int p, int hu, int hd, int h, int k) {
    hu = add(hu, mul(c[u], pow[h - 1]));
    if(p != -1) hd = add(mul(hd, base), c[u]);

    int tar = add(mul(hu, pow[k - h]), -hd);
    check[h][tar] = 1;

    for(int v : g[u]) {
        if(v == p || del[v]) continue;
        mark(v, u, hu, hd, h + 1, k);
    } 
}

bool buildcen(int u, int k) {
    calsize(u, -1);

    int root = findcen(u, -1, sze[u]);
    del[root] = 1;

    int maxdepth = 1;
    int tmp = c[root];
    tmp = mul(tmp, pow[k - 1]);
    check[1][tmp] = 1;

    for(int v : g[root]) {
        if(del[v]) continue;
        if(cal(v, root, c[root], 0, 2, k, maxdepth)) return true;
        mark(v, root, c[root], 0, 2, k);
    }

    FOR(i, 1, maxdepth) check[i].clear();

    for(int v : g[root]) {
        if(del[v]) continue;
        if(buildcen(v, k)) return true;
    }

    return false;
}

bool can(int k) {
    FOR(i, 1, n) {
        check[i].clear();
        del[i] = 0;
    }
    return buildcen(1, k);
}

void Solve() {
    pow[0] = 1;
    FOR(i, 1, n) pow[i] = mul(pow[i - 1], base);

    int res = 1;
    int l = 1, r = (n + 1) / 2;
    while(l <= r) {
        int mid = l + r >> 1;
        if(can(2 * mid - 1)) {
            res = max(res, 2 * mid - 1);
            l = mid + 1;
        }
        else r = mid - 1;
    } 
    l = 1, r = n / 2;
    while(l <= r) {
        int mid = l + r >> 1;
        if(can(2 * mid)) {
            res = max(res, 2 * mid);
            l = mid + 1;
        }
        else r = mid - 1;
    }

    cout << res << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int tc = 1;
    // cin >> tc;
    while(tc--) {
        cin >> n;
        FOR(i, 1, n) cin >> c[i];
        FOR(i, 1, n - 1) {
            int u, v; cin >> u >> v;
            g[u].pb(v);
            g[v].pb(u);
        }
        Solve();
    }
}

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