oj.uz

Submission #976955

# Submission time Handle Problem Language Result Execution time Memory
976955 2024-05-07T09:40:11 Z boyliguanhan Lampice (COCI19_lampice) C++17
110 / 110
 4442 ms 27100 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize(2)
gp_hash_table<int,int> mp[25010];
#define N 50010
#define int long long
int palin[N],vis[N],pw[N],hsh[N],sz[N],val[N],ans,rt,B=31,mod=1e9+7;
vector<int>adj[N],V{0};
void dfssz(int n,int p,int tot){
    palin[n]=0;
    int mx=0;
    sz[n]=1;
    for(auto i:adj[n])
        if(i-p&&!vis[i]) {
            dfssz(i,n,tot),
            sz[n]+=sz[i],
            mx=max(mx,sz[i]);
        }
    if(sz[n]*2>=tot&&mx*2<=tot)
        rt=n;
}
void dfshash(int n,int p){
    hsh[n]=(hsh[p]*B+val[n])%mod;
    for(auto i:adj[n])
        if(!vis[i]&&i-p)
            dfshash(i,n);
}
int MD;
void calcdfs(int n,int p,int l,int d,int h){
    MD=max(MD,d);
    if(d>l||ans) return;
    ans|=mp[d][(hsh[n]-val[V[1]]*pw[d]%mod+mod)%mod];
    h=(h+pw[d]*val[n])%mod;
    palin[n]=hsh[n]==h;
    for(auto i:adj[n])
        if(!vis[i]&&i-p)
            calcdfs(i,n,l,d+1,h);
}
void upddfs(int n,int p,int l,int d){
    if(ans||d>l) return;
    V.push_back(n);
    if(d+l/2>=l&&palin[V[2*d-l]])
        mp[l-d][(hsh[n]-hsh[V[2*d-l]]*pw[l-d]%mod+mod)%mod]=1;
    for(auto i:adj[n])
        if(i-p&&!vis[i])
            upddfs(i,n,l,d+1);
    V.pop_back();
}
void cent(int n,int s,int l){
    if(ans)
        return;
    MD=0;
    dfssz(n,0,s);
    dfssz(n=rt,0,s);
    palin[n]=1;
    dfshash(n,0);
    vis[n]=1;
    V.push_back(n);
    for(auto i:adj[n]) if(!vis[i])
        calcdfs(i,n,l,1,val[n]),
        upddfs(i,n,l,2);
    if(mp[0][0])
        ans=1;
    for(int i=0;i<=min(l/2,MD);i++)
        mp[i].clear();
    reverse(adj[n].begin(),adj[n].end());
    for(auto i:adj[n]) if(!vis[i])
        calcdfs(i,n,l,1,val[n]),
        upddfs(i,n,l,2);
    if(mp[0][0])
        ans=1;
    for(int i=0;i<=min(l/2,MD);i++)
        mp[i].clear();
    V.pop_back();
    for(auto i:adj[n])
        if(!vis[i])
            cent(i,sz[i],l);
}
signed main() {
    pw[0]=1;
    for(int i=1;i<N;i++)
        pw[i]=pw[i-1]*B%mod;
    cin.tie(0)->sync_with_stdio(0);
    int n;
    string str;
    cin>>n>>str;
    for(int i=1;i<=n;i++)
        val[i]=str[i-1]-'`';
    if(n==1)
        return puts("1"),0;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int l=0,r=n/2,CALLS=0;
    while(l<r){
        int mid=l+r+1>>1;
        for(int i=1;i<=n;i++)
            palin[i]=vis[i]=ans=0;
        cent(1,n,mid*2+1);
        CALLS++;
        if(ans)
            l=mid;
        else r=mid-1;
    }
    int l1=l,r1=n/2;
    while(l1<r1){
        int mid=l1+r1+1>>1;
        for(int i=1;i<=n;i++)
            palin[i]=vis[i]=ans=0;
        cent(1,n,mid*2);
        CALLS++;
        if(ans)
            l1=mid;
        else r1=mid-1;
    }
    cout<<max(l1*2,l*2+1)<<'\n';
}

Compilation message

lampice.cpp: In function 'int main()':
lampice.cpp:101:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:112:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  112 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9048 KB Output is correct
2 Correct 15 ms 9316 KB Output is correct
3 Correct 48 ms 9308 KB Output is correct
4 Correct 52 ms 9308 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 4 ms 9052 KB Output is correct
7 Correct 4 ms 9104 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1757 ms 22916 KB Output is correct
2 Correct 1846 ms 14804 KB Output is correct
3 Correct 1049 ms 14992 KB Output is correct
4 Correct 1079 ms 15028 KB Output is correct
5 Correct 1947 ms 17428 KB Output is correct
6 Correct 135 ms 15068 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3781 ms 27100 KB Output is correct
2 Correct 3692 ms 14396 KB Output is correct
3 Correct 4198 ms 13940 KB Output is correct
4 Correct 3704 ms 12588 KB Output is correct
5 Correct 3623 ms 12752 KB Output is correct
6 Correct 3298 ms 14504 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9048 KB Output is correct
2 Correct 15 ms 9316 KB Output is correct
3 Correct 48 ms 9308 KB Output is correct
4 Correct 52 ms 9308 KB Output is correct
5 Correct 4 ms 9048 KB Output is correct
6 Correct 4 ms 9052 KB Output is correct
7 Correct 4 ms 9104 KB Output is correct
8 Correct 1757 ms 22916 KB Output is correct
9 Correct 1846 ms 14804 KB Output is correct
10 Correct 1049 ms 14992 KB Output is correct
11 Correct 1079 ms 15028 KB Output is correct
12 Correct 1947 ms 17428 KB Output is correct
13 Correct 135 ms 15068 KB Output is correct
14 Correct 3781 ms 27100 KB Output is correct
15 Correct 3692 ms 14396 KB Output is correct
16 Correct 4198 ms 13940 KB Output is correct
17 Correct 3704 ms 12588 KB Output is correct
18 Correct 3623 ms 12752 KB Output is correct
19 Correct 3298 ms 14504 KB Output is correct
20 Correct 2174 ms 12292 KB Output is correct
21 Correct 2335 ms 13284 KB Output is correct
22 Correct 3969 ms 12904 KB Output is correct
23 Correct 734 ms 11348 KB Output is correct
24 Correct 2734 ms 12376 KB Output is correct
25 Correct 3466 ms 12040 KB Output is correct
26 Correct 4442 ms 13780 KB Output is correct
27 Correct 4130 ms 22616 KB Output is correct
28 Correct 2638 ms 11232 KB Output is correct
29 Correct 2777 ms 11256 KB Output is correct
30 Correct 3506 ms 12540 KB Output is correct
31 Correct 3469 ms 11680 KB Output is correct
32 Correct 2614 ms 13816 KB Output is correct
33 Correct 1899 ms 12960 KB Output is correct