Submission #1223699

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223699		Dreamy_lovesper	Lampice (COCI19_lampice)	C++20	42 / 110	5094 ms	100392 KiB

lampice

#include <bits/stdc++.h>

using namespace std;

// Do you think you'll ever remember me someday, or will I just fade away from your memory?
#define LIFESUCK ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define str string
#define mll map<ll, ll>
#define vll vector<ll>
#define pll pair<ll, ll>
#define fi first 
#define se second 
#define all(c) c.begin(), c.end()
#define pb push_back
#define debug cout << "I Love You\n";
#define fu(i, a, b) for (int i = a; i <= b; i++)
#define fd(i, b, a) for (int i = b; i >= a; i--)
#define Bitc(msk, j) ((msk >> j) & 1)
#define _log(x) 31 - __builtin_clz(x)

const ll Mod = 1e9 + 7;
const ll inf = (1ll << 30);
const ll lnf = (1ll << 60);

// When time passes and things change... will you still remember someone like me?
int64_t add(ll &a, ll b) {
    a += b;
    if (a >= Mod) a %= Mod;
    while (a < 0) a += Mod;
    return a;
}
int64_t mul(ll a, ll b) {
    a = 1ll * a * b % Mod;
    return a;
}

template <class X, class Y>
bool minimize(X &x, Y y) {
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template <class X, class Y>
bool maximize(X &x, Y y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

// I wonder… will I just become a distant memory to you one day?
#define mxn 200'007
ll n, len;
str s;
vll graph[mxn];

struct Edge{
    ll u, v;
} edge[mxn];

namespace Love1 {
    bool check () {
        return (n <= 3000);
    }

    vector<char> t;
    const ll base = 37;
    ll f[3007][3007], g[3007][3007];

    void dfs(ll u, ll p, ll *f, ll *g) {
        for(auto &v: graph[u]) {
            if(v == p) continue;
            f[v] = f[u] + 1;
            g[v] = (g[u] * base + s[v]) % Mod;       
            dfs(v, u, f, g);
        }
    }

    void DreamyLove() {
        ll sad = 1;
        
        fu(u, 1, n) dfs(u, 0, f[u], g[u]);

        fu(u, 1, n) fu(v, u + 1, n) if(g[u][v] == g[v][u]) maximize(sad, f[u][v] + 1);
        cout << sad;
    }
}

namespace Love2 {
    bool check () {
        ll cr = 0;
        fu(i, 1, n) cr += (graph[i].size() == 1);
        return (cr == 2);
    }

    ll f[mxn];
    void DreamyLove () {

        ll sad = 0;
        ll rgh = 0, center = 0;

        str t = "#";
        for(auto&i: s) {
            t += i;
            t += '#';
        }

        ll n = t.size();
        fu(i, 1, n) {
            if(i < rgh) f[i] = min(rgh - i, f[2 * center - i]);
            while(i - f[i] - 1 >= 0 && i + f[i] + 1 < n && t[i - f[i] - 1] == t[i + f[i] + 1]) f[i]++;
            if(i + f[i] > rgh) center = i, rgh = i + f[i];
            maximize(sad, f[i]);
        }

        cout << sad;

        //
    }
}

namespace Love3 {
    bool check () {
        fu(i, 1, n) if(graph[i].size() > 101) return 0;
        return 1;
    }

    ll sad = 0;
    str st;
    bool dfs(ll u, ll p, ll end) {
        if(u == end) return 1;
        for(auto&v: graph[u]) {
            if(v == p) continue;
            if(dfs(v, u, end)) {st += s[v]; return 1;}
        }
        return 0;
    }

    void Calc() {
        ll rgh = 0, center = 0;

        str t = "#";
        for(auto&i: st) {
            t += i;
            t += '#';
        }

        ll n = t.size();
        vll f(n + 1, 0);
        fu(i, 1, n) {
            if(i < rgh) f[i] = min(rgh - i, f[2 * center - i]);
            while(i - f[i] - 1 >= 0 && i + f[i] + 1 < n && t[i - f[i] - 1] == t[i + f[i] + 1]) f[i]++;
            if(i + f[i] > rgh) center = i, rgh = i + f[i];
            maximize(sad, f[i]);
        }
    }

    void DreamyLove () {

        vll c;
        fu(i, 1, n) if(graph[i].size() == 1) c.pb(i);

        fu(u, 0, c.size() - 1)
            fu(v, u + 1, c.size() - 1) {
                st = "";
                dfs(c[u], 0, c[v]);
                st += s[c[u]];
                // cerr << c[u] << ' ' << c[v] << "  " << st << '\n';
                Calc();
            }

            cout << sad;

        //
    }
}

void lovesper(const ll &TestCase) {
    
    cin >> n >> s;
    len = s.size(); s = '#' + s;
    fu(i, 2, n) {
        ll u, v; cin >> u >> v;
        graph[u].pb(v);
        graph[v].pb(u);
        edge[i] = {u, v};
    }

    if(Love1::check()) {
        Love1::DreamyLove();
        return;
    }

    if(Love2::check()) {
        Love2::DreamyLove();
        return;
    }

    if(Love3::check()) {
        Love3::DreamyLove();
        return;
    }

}

signed main() {
    LIFESUCK

    #define name "lovesper"
    // freopen(name".inp", "r", stdin);
    // freopen(name".out", "w", stdout);
    
    ll Test = 1;
    // cin >> Test;

    fu(i, 1, Test) {
        lovesper(i);
        if (i < Test) cout << '\n';
    }

    return 0;
}

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