oj.uz

Submission #976961

# Submission time Handle Problem Language Result Execution time Memory
976961 2024-05-07T09:45:28 Z boyliguanhan Lampice (COCI19_lampice) C++17
110 / 110
 4562 ms 29000 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;
}
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);
    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;
    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;
    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:100:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:110:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4952 KB Output is correct
2 Correct 12 ms 4956 KB Output is correct
3 Correct 44 ms 5208 KB Output is correct
4 Correct 43 ms 5208 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 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 1767 ms 29000 KB Output is correct
2 Correct 1727 ms 13264 KB Output is correct
3 Correct 1004 ms 13036 KB Output is correct
4 Correct 1046 ms 13016 KB Output is correct
5 Correct 1831 ms 17100 KB Output is correct
6 Correct 142 ms 12124 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3735 ms 27956 KB Output is correct
2 Correct 3559 ms 11680 KB Output is correct
3 Correct 4073 ms 11644 KB Output is correct
4 Correct 3423 ms 9408 KB Output is correct
5 Correct 3354 ms 9464 KB Output is correct
6 Correct 3392 ms 11612 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4952 KB Output is correct
2 Correct 12 ms 4956 KB Output is correct
3 Correct 44 ms 5208 KB Output is correct
4 Correct 43 ms 5208 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1767 ms 29000 KB Output is correct
9 Correct 1727 ms 13264 KB Output is correct
10 Correct 1004 ms 13036 KB Output is correct
11 Correct 1046 ms 13016 KB Output is correct
12 Correct 1831 ms 17100 KB Output is correct
13 Correct 142 ms 12124 KB Output is correct
14 Correct 3735 ms 27956 KB Output is correct
15 Correct 3559 ms 11680 KB Output is correct
16 Correct 4073 ms 11644 KB Output is correct
17 Correct 3423 ms 9408 KB Output is correct
18 Correct 3354 ms 9464 KB Output is correct
19 Correct 3392 ms 11612 KB Output is correct
20 Correct 2545 ms 7836 KB Output is correct
21 Correct 2994 ms 9384 KB Output is correct
22 Correct 4484 ms 8996 KB Output is correct
23 Correct 819 ms 7192 KB Output is correct
24 Correct 2616 ms 8864 KB Output is correct
25 Correct 3296 ms 8032 KB Output is correct
26 Correct 4186 ms 11240 KB Output is correct
27 Correct 4562 ms 21148 KB Output is correct
28 Correct 2545 ms 7260 KB Output is correct
29 Correct 2598 ms 7196 KB Output is correct
30 Correct 3220 ms 9204 KB Output is correct
31 Correct 3009 ms 8092 KB Output is correct
32 Correct 2862 ms 9924 KB Output is correct
33 Correct 2642 ms 9040 KB Output is correct