Submission #311223

#	Time	Username	Problem	Language	Result	Execution time	Memory
311223		Vladikus004	Lampice (COCI19_lampice)	C++14	42 / 110	196 ms	75384 KiB

lampice

#include <bits/stdc++.h>
#define inf 2e9
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 50000 + 3, P = 31;
int n;
vector <int> v[N];
string s;
ull h[3002][3002];
int dst[3002][3002];
ull hs[N], deg[N];
ull rhs[N], rdeg[N];

void dfs(int st, int x, int pr){
    if (x == st) h[x][x] = s[x] - 'a' + 1, dst[x][x] = 0;
    for (auto u: v[x]){
        if (u == pr) continue;
        dst[st][u] = dst[st][x] + 1;
        h[st][u] = h[st][x] * P + (s[u] - 'a' + 1);
        dfs(st, u, x);
    }
}

void solve1(){
    for (int i = 0; i < n; i++)
        dfs(i, i, -1);
    int mx = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (h[i][j] == h[j][i]){
                mx = max(mx, dst[i][j]);
            }
    cout << mx + 1;
    return;
}

void prec(){
    hs[0] = s[0] - 'a' + 1;
    deg[0] = 1;
    for (int i = 1; i < s.size(); i++){
        hs[i] = hs[i - 1] * P + s[i] - 'a' + 1;
        deg[i] = deg[i - 1] *  P;
    }
    reverse(all(s));
    rhs[0] = s[0] - 'a' + 1;
    rdeg[0] = 1;
    for (int i = 1; i < s.size(); i++){
        rhs[i] = rhs[i - 1] * P + s[i] - 'a' + 1;
        rdeg[i] = rdeg[i - 1] * P;
    }
    reverse(all(s));
}

ull get_rh(int l, int r){
    l = n - 1 - l;
    r = n - 1 - r;
    swap(l, r);
    if (!l) return rhs[r];
    return rhs[r] - rhs[l - 1] * rdeg[r - l + 1];
}

ull get_h(int l, int r){
    if (!l) return hs[r];
    return hs[r] - hs[l - 1] * deg[r - l + 1];
}

bool is_pal(int l, int r){
    if (l > r) return false;
    return get_h(l, r) == get_rh(l, r);
}

void solve2(){
    int ans = 1;
    for (int i = 0; i < n; i++){
        int l = 0, r = min(i, n - i - 1) + 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (is_pal(i - mid, i + mid)) l = mid + 1;
            else r = mid;
        }
        --l;
        ans = max(ans, l * 2 + 1);
    }
    for (int i = 1; i < n; i++){
        int l = 0, r = min(i, n - i) + 1;
        while (l < r){
            int mid = (l + r) / 2;
            if (is_pal(i - mid, i + mid - 1)) l = mid + 1;
            else r = mid;
        }
        --l;
        ans = max(ans, l * 2);
    }
    cout << ans;
    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> s;
    prec();
    for (int i = 0; i < n - 1; i++){
        int x, y;
        cin >> x >> y;
        --x; --y;
        v[x].pb(y);
        v[y].pb(x);
    }
//    cout << get_h(2, 4) << " " << get_rh(2, 4) << "!\n";
//    return 0;
    if (n <= 3000){
        solve1();
    }else{
        solve2();
    }
}

Compilation message (stderr)

lampice.cpp: In function 'void prec()':
lampice.cpp:46:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i = 1; i < s.size(); i++){
      |                     ~~^~~~~~~~~~
lampice.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for (int i = 1; i < s.size(); i++){
      |                     ~~^~~~~~~~~~

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