oj.uz

Submission #976953

# Submission time Handle Problem Language Result Execution time Memory
976953 2024-05-07T09:37:09 Z boyliguanhan Lampice (COCI19_lampice) C++17
110 / 110
 4684 ms 29268 KB 
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
unordered_map<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:100:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:111:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  111 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5208 KB Output is correct
2 Correct 10 ms 5212 KB Output is correct
3 Correct 36 ms 5496 KB Output is correct
4 Correct 41 ms 5468 KB Output is correct
5 Correct 2 ms 5208 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2013 ms 29268 KB Output is correct
2 Correct 1776 ms 15332 KB Output is correct
3 Correct 1032 ms 15440 KB Output is correct
4 Correct 1031 ms 15560 KB Output is correct
5 Correct 1784 ms 19580 KB Output is correct
6 Correct 167 ms 15316 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4684 ms 27412 KB Output is correct
2 Correct 3242 ms 12244 KB Output is correct
3 Correct 3766 ms 12624 KB Output is correct
4 Correct 3512 ms 10784 KB Output is correct
5 Correct 3087 ms 10124 KB Output is correct
6 Correct 2917 ms 12372 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5208 KB Output is correct
2 Correct 10 ms 5212 KB Output is correct
3 Correct 36 ms 5496 KB Output is correct
4 Correct 41 ms 5468 KB Output is correct
5 Correct 2 ms 5208 KB Output is correct
6 Correct 2 ms 5212 KB Output is correct
7 Correct 3 ms 5212 KB Output is correct
8 Correct 2013 ms 29268 KB Output is correct
9 Correct 1776 ms 15332 KB Output is correct
10 Correct 1032 ms 15440 KB Output is correct
11 Correct 1031 ms 15560 KB Output is correct
12 Correct 1784 ms 19580 KB Output is correct
13 Correct 167 ms 15316 KB Output is correct
14 Correct 4684 ms 27412 KB Output is correct
15 Correct 3242 ms 12244 KB Output is correct
16 Correct 3766 ms 12624 KB Output is correct
17 Correct 3512 ms 10784 KB Output is correct
18 Correct 3087 ms 10124 KB Output is correct
19 Correct 2917 ms 12372 KB Output is correct
20 Correct 1918 ms 8788 KB Output is correct
21 Correct 2215 ms 10340 KB Output is correct
22 Correct 3486 ms 9664 KB Output is correct
23 Correct 655 ms 7920 KB Output is correct
24 Correct 2446 ms 9972 KB Output is correct
25 Correct 3179 ms 9124 KB Output is correct
26 Correct 3896 ms 12172 KB Output is correct
27 Correct 4064 ms 21144 KB Output is correct
28 Correct 2679 ms 8032 KB Output is correct
29 Correct 2690 ms 8092 KB Output is correct
30 Correct 3314 ms 10752 KB Output is correct
31 Correct 3249 ms 9096 KB Output is correct
32 Correct 2726 ms 12036 KB Output is correct
33 Correct 1554 ms 9668 KB Output is correct