oj.uz

Submission #977664

# Submission time Handle Problem Language Result Execution time Memory
977664 2024-05-08T08:48:47 Z boyliguanhan Lampice (COCI19_lampice) C++17
110 / 110
 4563 ms 29060 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
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;
}
int MD;
void calcdfs(int n,int p,int l,int d,int h){
    MD=max(MD,d);
    if(d>l||ans) return;
    hsh[n]=(hsh[p]*B+val[n])%mod;
    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);
    int c;
    if(d+l/2>=l&&palin[c=V[2*d-l]])
        mp[l-d][(hsh[n]-hsh[c]*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;
    vis[n]=1;
    hsh[n]=val[n];
    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;
    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);
        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);
        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:95:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:105:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  105 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4956 KB Output is correct
2 Correct 12 ms 4952 KB Output is correct
3 Correct 42 ms 5304 KB Output is correct
4 Correct 40 ms 5212 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1673 ms 29060 KB Output is correct
2 Correct 1691 ms 13264 KB Output is correct
3 Correct 999 ms 13656 KB Output is correct
4 Correct 1016 ms 13596 KB Output is correct
5 Correct 1882 ms 17756 KB Output is correct
6 Correct 138 ms 12764 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3585 ms 27960 KB Output is correct
2 Correct 3485 ms 12280 KB Output is correct
3 Correct 3941 ms 12308 KB Output is correct
4 Correct 3328 ms 10176 KB Output is correct
5 Correct 3459 ms 9996 KB Output is correct
6 Correct 3002 ms 11964 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4956 KB Output is correct
2 Correct 12 ms 4952 KB Output is correct
3 Correct 42 ms 5304 KB Output is correct
4 Correct 40 ms 5212 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1673 ms 29060 KB Output is correct
9 Correct 1691 ms 13264 KB Output is correct
10 Correct 999 ms 13656 KB Output is correct
11 Correct 1016 ms 13596 KB Output is correct
12 Correct 1882 ms 17756 KB Output is correct
13 Correct 138 ms 12764 KB Output is correct
14 Correct 3585 ms 27960 KB Output is correct
15 Correct 3485 ms 12280 KB Output is correct
16 Correct 3941 ms 12308 KB Output is correct
17 Correct 3328 ms 10176 KB Output is correct
18 Correct 3459 ms 9996 KB Output is correct
19 Correct 3002 ms 11964 KB Output is correct
20 Correct 2601 ms 8400 KB Output is correct
21 Correct 3206 ms 9944 KB Output is correct
22 Correct 4495 ms 9564 KB Output is correct
23 Correct 863 ms 7740 KB Output is correct
24 Correct 2373 ms 9432 KB Output is correct
25 Correct 3085 ms 8616 KB Output is correct
26 Correct 4003 ms 11660 KB Output is correct
27 Correct 4563 ms 22088 KB Output is correct
28 Correct 2312 ms 7768 KB Output is correct
29 Correct 2393 ms 7828 KB Output is correct
30 Correct 2968 ms 9808 KB Output is correct
31 Correct 2946 ms 8816 KB Output is correct
32 Correct 2665 ms 10476 KB Output is correct
33 Correct 2367 ms 9656 KB Output is correct