oj.uz

Submission #859114

# Submission time Handle Problem Language Result Execution time Memory
859114 2023-10-09T18:10:24 Z ZeroCool Lampice (COCI19_lampice) C++14
110 / 110
 1965 ms 12028 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 19 ms 2904 KB Output is correct
4 Correct 27 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 911 ms 9820 KB Output is correct
2 Correct 1329 ms 10424 KB Output is correct
3 Correct 738 ms 11460 KB Output is correct
4 Correct 850 ms 12028 KB Output is correct
5 Correct 1366 ms 11864 KB Output is correct
6 Correct 131 ms 11084 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1583 ms 9808 KB Output is correct
2 Correct 1922 ms 9308 KB Output is correct
3 Correct 1965 ms 9296 KB Output is correct
4 Correct 1830 ms 8688 KB Output is correct
5 Correct 1801 ms 8700 KB Output is correct
6 Correct 1577 ms 8204 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2396 KB Output is correct
2 Correct 5 ms 2652 KB Output is correct
3 Correct 19 ms 2904 KB Output is correct
4 Correct 27 ms 2652 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 911 ms 9820 KB Output is correct
9 Correct 1329 ms 10424 KB Output is correct
10 Correct 738 ms 11460 KB Output is correct
11 Correct 850 ms 12028 KB Output is correct
12 Correct 1366 ms 11864 KB Output is correct
13 Correct 131 ms 11084 KB Output is correct
14 Correct 1583 ms 9808 KB Output is correct
15 Correct 1922 ms 9308 KB Output is correct
16 Correct 1965 ms 9296 KB Output is correct
17 Correct 1830 ms 8688 KB Output is correct
18 Correct 1801 ms 8700 KB Output is correct
19 Correct 1577 ms 8204 KB Output is correct
20 Correct 980 ms 7296 KB Output is correct
21 Correct 1146 ms 8380 KB Output is correct
22 Correct 1827 ms 8408 KB Output is correct
23 Correct 363 ms 6728 KB Output is correct
24 Correct 1159 ms 7892 KB Output is correct
25 Correct 1413 ms 7564 KB Output is correct
26 Correct 1841 ms 9212 KB Output is correct
27 Correct 1738 ms 8912 KB Output is correct
28 Correct 1103 ms 7256 KB Output is correct
29 Correct 1144 ms 7244 KB Output is correct
30 Correct 1618 ms 8592 KB Output is correct
31 Correct 1361 ms 7608 KB Output is correct
32 Correct 1367 ms 9248 KB Output is correct
33 Correct 927 ms 8596 KB Output is correct