oj.uz

Submission #1098349

# Submission time Handle Problem Language Result Execution time Memory
1098349 2024-10-09T10:21:03 Z hiensumi Lampice (COCI19_lampice) C++14
0 / 110
 5000 ms 14172 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
#define fod(i,a,b) for(int i = (int) (a); i <= (int) (b); i++)
#define fok(i,a,b) for(int i = (int) (a); i >= (int) (b); i--)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define el '\n'
#define ve vector
#define vi ve<int>
#define vll ve<ll>
#define mask(a) (1LL<<(a))
#define BIT(msk,i) (msk>>(i)&1LL)
using namespace std;
template <class T> bool mini(T &a, T b){ return (a > (b)) ? a = (b), 1 : 0; }
template <class T> bool maxi(T &a, T b){ return (a < (b)) ? a = (b), 1 : 0; }
#define name "lampice"

mt19937 rng((uint64_t) new char);
ll rd(ll l, ll r){
    return uniform_int_distribution<ll>(l, r)(rng);
}

int n;
ve <vi> g;

const int N = 5e4;
char a[N + 5];

const int MOD = 1e9 + 3777;
const int base = 333;

int sz[N + 5];
bool del[N + 5];

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

int root_size = 0;
int get_cent(int u, int p){
    for(int v : g[u]) if(v != p and !del[v] and 2 * sz[v] > root_size) return get_cent(v, u);
    return u;
}

int base_pw[N + 5];

struct Node{
    int u;
    int cur, rev;
};

int sz_nodes = 0;
Node nodes[N + 5];

int len = 0;

/*
cur, rev: current string and its reversed string
cur_, rev_: another string
khi merge 2 đoạn thẳng ta được palindrome khi:
result_cur = result_rev

<=> rev * base^(len-h[u]) + cur_ = rev_ * base^(h[u]+1) + cur

<=> rev_ * base^(h[u]) - cur_ = rev * base^(len-h[u]) - cur
*/

int h[N + 5], cur[N + 5], rev[N + 5];

unordered_set <int> f[N + 5];

bool found = 0;
void dfs(int u, int p, bool ok){
    if(!ok){

        h[u] = h[p] + 1;
        cur[u] = (1LL * cur[p] * base % MOD + a[u]) % MOD;
        rev[u] = (1LL * a[u] * base_pw[h[u]] % MOD + rev[p]) % MOD;

        int x = (1LL * rev[u] * base_pw[len - h[u]] - cur[u]) % MOD;
        if(x < 0) x += MOD;

        if(cur[u] == rev[u] and h[u] + 1 == len){
            found = 1;
            return;
        }

        if(f[len - h[u] - 1].find(x) != f[len - h[u]- 1].end()){
            found = 1;
            return;
        }
    }
    else{
        int x = (1LL * rev[u] * base_pw[len - h[u]] - cur[u]) % MOD;
        if(x < 0) x += MOD;
        f[h[u]].insert(x);
    }

    if(h[u] == len - 1) return;

    for(int v : g[u]) if(v != p and !del[v]){
        dfs(v, u, ok);
        if(found) return;
    }
}

bool solve_tree(int r){
    fod(i,0,len) f[i].clear();

    h[r] = 0;
    cur[r] = rev[r] = a[r];

    found = 0;

    for(int v : g[r]) if(!del[v]){
        dfs(v, r, 0);
        if(found) return 1;
        dfs(v, r, 1);
    }

    return 0;
}

bool dec(int u){
    find_size(u, 0);
    root_size = sz[u];
    int c = get_cent(u, 0);

    if(solve_tree(c)) return 1;

    del[c] = 1;
    for(int v : g[c]) if(!del[v]){
        if(dec(v)) return 1;
    }
    return 0;
}

bool check(int l){
    if(l > n) return 0;
    if(l == 1) return 1;

    len = l;
    fod(i,0,n) del[i] = 0;
    return dec(1);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    fod(i,1,n) cin >> a[i], a[i] -= 96;

    {
        g.resize(n + 1);
        int u, v;
        fod(i,1,n-1){
            cin >> u >> v;
            g[u].pb(v);
            g[v].pb(u);
        }
    }

    base_pw[0] = 1;
    fod(i,1,n) base_pw[i] = 1LL * base_pw[i-1] * base % MOD;

//    cout << check(4) << el;

    int res = 0;

    int l = 0, r = n;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(2 * mid + 1)) maxi(res, 2 * mid + 1), l = mid + 1;
        else r = mid - 1;
    }

    l = 1, r = n;
    while(l <= r){
        int mid = l + r >> 1;
        if(check(2 * mid)) maxi(res, 2 * mid), l = mid + 1;
        else r = mid - 1;
    }

    cout << res;

    return 0;
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:178:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  178 |         int mid = l + r >> 1;
      |                   ~~^~~
lampice.cpp:185:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  185 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5036 ms 14172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5100 ms 11864 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

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