Submission #1294053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294053		lmaobruh	Lampice (COCI19_lampice)	C++20	56 / 110	2947 ms	80508 KiB

lampice

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define pb push_back
#define fi first
#define se second
#define ii pair<int,int>
#define ve vector
#define all(x) x.begin(), x.end()
#define fo(i,a,b) for (int i=(a); i<=(b); ++i)
#define fd(i,a,b) for (int i=(a); i>=(b); --i)
#define maxi(a, b) a = max(a, b)
#define mini(a, b) a = min(a, b)
#define siz(x) ((int)(x).size())
#define vi ve<int>
#define _ << ' ' <<

const int N = 1e6+5, inf = 1e9+10, mod1 = 1e9+7, base = 11111;

/**

**/

bool MBE;

int bpw(int a, int b) {
    int res = 1;
    for (; b; b>>=1, a=1LL*a*a%mod1)
        if (b&1) res=1LL*res*a%mod1;
    return res;
}

struct H {
    int val;
    H(){val=0;}
    H(int x){val=x;if(val>=mod1)val-=mod1;}
    H operator+(H x) {return H(val+x.val);}
    H operator*(H x) {return H(1LL*val*x.val%mod1);}
    H operator-(H x) {return H(val-x.val+mod1);}
    H operator/(H x) {return H(1LL*val*bpw(x.val, mod1-2)%mod1);}
    bool operator==(H x) {return val==x.val;}
    int toInt() {return val;}
};

int n, a[N], len, sz[N], maxH;
vi g[N]; bool del[N], pal[N];
H down[N], up[N], pw[N];
unordered_set<int> f[N];

void dfs(int u, int p = -1) {
    sz[u] = 1;
    for (int v : g[u]) if (v!=p&&!del[v]) {
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int findcen(int u, int p, int tot) {
    for (int v : g[u]) if (v!=p&&!del[v]&&sz[v]*2>tot)
        return findcen(v, u, tot);
    return u;
}

int stk[N], Head;

bool find(int u, int p, int h, H hu, H hd) {
    maxi(maxH, h);
    if (h > len) return 0;
    stk[++Head] = u;
    hd = hd * base + a[u];
    hu = hu + pw[h-1] * a[u];
    down[u] = hd, up[u] = hu;
    pal[u] = (hu == hd);
    if (pal[u] && h == len) return 1;
    if (h * 2 >= len) {
        int need = len - h;
        int x = stk[Head - need];
        if (pal[x]) {
            H cur = (hd - down[x] * pw[need]);
            if (f[need].count(cur.toInt()))
                return 1;
        }
    }
    for (int v:g[u]) if (v!=p&&!del[v])
        if (find(v, u, h+1, hu, hd))
            return 1;
    Head--;
    return 0;
}

void ins(int u, int p, int h, H hu, H hd) {
    maxi(maxH, h);
    if (h * 2 > len) return;
    hd = hd * base + a[u];
    f[h].insert(hd.toInt());
    for (int v:g[u]) if (v!=p&&!del[v])
        ins(v, u, h+1, hu, hd);
}

bool go(int u) {
    if (len == 1) return 1;

    dfs(u);
    int cen = findcen(u, -1, sz[u]);
    del[cen] = 1;
    maxH = 0;

    down[cen] = up[cen] = H(a[cen]); pal[cen]=1;
    stk[++Head] = cen;
    for (int v:g[cen]) if (!del[v]) {
        if (find(v, cen, 2, H(a[cen]), H(a[cen]))) {
            return 1;
        }
        ins(v, cen, 1, H(0), H(0));
    }
    Head = 0;
    fo(i,0,maxH) f[i].clear();

    reverse(all(g[cen]));
    stk[++Head] = cen;
    for (int v:g[cen]) if (!del[v]) {
        if (find(v, cen, 2, H(a[cen]), H(a[cen]))) {
            return 1;
        }
        ins(v, cen, 1, H(0), H(0));
    }
    Head = 0;

    fo(i,0,maxH) f[i].clear();
    for (int v:g[cen]) if (!del[v]&&go(v)) return 1;
    return 0;
}

bool check(int x) {
    fo(i,1,n) f[i].clear(), del[i]=0, pal[i]=0;
    len = x;
    return go(1);
}

void sol() {
    cin >> n;
    pw[0]=1;
    fo(i,1,n) pw[i]=pw[i-1]*base;
    fo(i,1,n) {
        char c; cin >> c;
        a[i] = c-'a'+1;
    }
    fo(i,1,n-1) {
        int u, v; cin >> u >> v;
        g[u].pb(v), g[v].pb(u);
    }
    int l = 0, r = n / 2, mid, res = 0;
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(2*mid)) {
            maxi(res, 2*mid);
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    l = 0, r = n / 2, mid;
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(2 * mid + 1)) {
            maxi(res, 2*mid+1);
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    cout << res;
}

bool MED;

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    if(fopen("A.inp","r")) {
        freopen("A.inp","r",stdin);
        freopen("A.out","w",stdout);
    }
    int tc = 1; // cin >> tc;
    fo(i,1,tc) sol();
//    cerr << "Memory = " << abs(&MED - &MBE)/1024.0/1024.0 << " MB";
    return 0;
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:181:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |         freopen("A.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~
lampice.cpp:182:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |         freopen("A.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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