oj.uz

Submission #311223

# Submission time Handle Problem Language Result Execution time Memory
311223 2020-10-09T16:56:02 Z Vladikus004 Lampice (COCI19_lampice) C++14
42 / 110
 196 ms 75384 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5760 KB Output is correct
2 Correct 19 ms 14976 KB Output is correct
3 Correct 82 ms 40440 KB Output is correct
4 Correct 196 ms 75384 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4864 KB Output is correct
2 Correct 24 ms 4864 KB Output is correct
3 Correct 23 ms 4992 KB Output is correct
4 Correct 25 ms 5120 KB Output is correct
5 Correct 25 ms 5376 KB Output is correct
6 Correct 24 ms 5376 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 5292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5760 KB Output is correct
2 Correct 19 ms 14976 KB Output is correct
3 Correct 82 ms 40440 KB Output is correct
4 Correct 196 ms 75384 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct
8 Correct 22 ms 4864 KB Output is correct
9 Correct 24 ms 4864 KB Output is correct
10 Correct 23 ms 4992 KB Output is correct
11 Correct 25 ms 5120 KB Output is correct
12 Correct 25 ms 5376 KB Output is correct
13 Correct 24 ms 5376 KB Output is correct
14 Incorrect 29 ms 5292 KB Output isn't correct
15 Halted 0 ms 0 KB -