Submission #859114

#	Time	Username	Problem	Language	Result	Execution time	Memory
859114		ZeroCool	Lampice (COCI19_lampice)	C++14	110 / 110	1965 ms	12028 KiB

lampice

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(g) g.begin(), g.end()
#define rall(g) g.rbegin(), g.rend()

using ll = long long;
using ld = long double;
 
void solve(int T);
void pre();
 
const int N = 5e4 + 5;
const int M = 405;
const int SQRT = 500;
const int LOG = 20;
const int INF = 1e18;
const int MOD = 1e9 + 7;
const ld EPS = 1e-9;
const int BASE = 9973;

void pre(){
	
    ios::sync_with_stdio(false);
    cin.tie(0);
	
	
}

int32_t main(){
	pre();
	int tt = 1;
	//cin>>tt;
	for(int i = 1;i<=tt;i++){
		cerr<<"Case "<<i<<": "<<endl;
		solve(i);
	}
    return 0;
}

int n, m, h;
int color[N];
int po[N];
int curlen, cursz;
int sz[N], curdn[N]; 
int up[N], down[N], dep[N];

vector<int> g[N];
bool del[N];
bool ispal[N];
bool bb;

set<int> hashes_s, hashes_l;
vector<int> toadd_s, toadd_l;

int fh(int dx, int dy, int hx, int hy){ 
    int dif = dy - dx;
    return (hy - (hx * po[dif]) % MOD + 2 * MOD) % MOD;
}

void dfs(int x, int p){
    sz[x] = 1;
    for(int u : g[x]){
        if(u == p || del[u])continue;
        dfs(u, x);
        sz[x] += sz[u];
    }
}

int cen(int x, int p){
    for(int u : g[x]){
        if(del[u] || u == p)continue;
        if(sz[u] * 2 > cursz)return cen(u, x);
    }
    return x;
}

void dfs2(int x, int p){
    if(bb)return;
    if(dep[x] > curlen)return;
    down[x] = (down[p] * BASE + color[x]) % MOD; 
    up[x] = (up[p] + po[dep[x]] * color[x]) % MOD;
    curdn[dep[x]] = x; 
    ispal[x] = (up[x] == down[x]); 

    if(dep[x] == curlen){
        if(ispal[x])bb = true;
    }
    else if(dep[x] > curlen / 2){ 
        int dif = 2 * dep[x] - curlen;
        int c = curdn[dif];
        int pc = curdn[dif - 1];

        
        if(ispal[c]){
            int hn = fh(dep[c] - 1, dep[x], down[pc], down[x]);
            if(hashes_s.count(hn))bb = true;
            toadd_l.pb(hn);
        }
    }
    else {
        if(hashes_l.count(down[x])){
            bb = true;
        }
        toadd_s.pb(down[x]);
    }

    if(dep[x] * 2 == curlen){ 
        if(hashes_s.count(down[x]))bb = true;
    }

    for(int u : g[x]){
        if(del[u] || u == p)continue;
        dep[u] = dep[x] + 1;
        dfs2(u, x);
    }
}

void decomp(int x){
    if(bb)return;
    dfs(x, 0);
    cursz = sz[x];
    int C = cen(x, 0);
    dep[C] = 0;
    up[C] = down[C] = color[C];
    del[C] = 1;
    curdn[0] = C;

    for(int u : g[C]){
        if(!del[u]){
            dep[u] = 1;
            dfs2(u, C);
            while(toadd_s.size()){
                int t = toadd_s.back();
                toadd_s.pop_back();
                hashes_s.insert(t);
            }
            while(toadd_l.size()){
                int t = toadd_l.back();
                toadd_l.pop_back();
                hashes_l.insert(t);
            }
        }
    }
   
    hashes_s.clear(); 
    hashes_l.clear();

    for(int u : g[C]){
        if(!del[u]){
            decomp(u);
        }
    }
}

bool ok(int x){ 
    if(x == 1)return 1;
    curlen = x - 1;
    memset(del, 0, n + 1);
    bb = 0;
    decomp(1);

    return bb;
}

void solve(int T){
    cin>>n;
    string s;
    cin>>s;
    for(int i = 0;i<n;i++){
        color[i + 1] = s[i] - 'a' + 1;
    }

    po[0] = 1;
    for(int i = 1;i<=n;i++)po[i] = (po[i - 1] * BASE) % MOD;
    for(int i = 1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }

    int l = 0;
    int r = n / 2 - (n % 2 == 0);
    int ans=0;
    while(r >= l){
        int mid = (r + l) / 2;
        if(ok(mid * 2 + 1)){
            ans = max(ans, mid * 2 + 1);
            l = mid + 1;
        }
        else {
            r = mid - 1;
        }
    }

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

    cout<<ans;
}   

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