oj.uz

Submission #977666

# Submission time Handle Problem Language Result Execution time Memory
977666 2024-05-08T08:55:00 Z boyliguanhan Lampice (COCI19_lampice) C++17
110 / 110
 2457 ms 28848 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(s<l) return;
    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:96:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:106:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 7 ms 4956 KB Output is correct
3 Correct 22 ms 5208 KB Output is correct
4 Correct 16 ms 5208 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 28848 KB Output is correct
2 Correct 261 ms 12924 KB Output is correct
3 Correct 254 ms 13136 KB Output is correct
4 Correct 257 ms 13388 KB Output is correct
5 Correct 314 ms 16868 KB Output is correct
6 Correct 58 ms 12120 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1517 ms 27972 KB Output is correct
2 Correct 1044 ms 11880 KB Output is correct
3 Correct 1075 ms 11900 KB Output is correct
4 Correct 637 ms 9568 KB Output is correct
5 Correct 677 ms 9304 KB Output is correct
6 Correct 901 ms 11752 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5208 KB Output is correct
2 Correct 7 ms 4956 KB Output is correct
3 Correct 22 ms 5208 KB Output is correct
4 Correct 16 ms 5208 KB Output is correct
5 Correct 2 ms 4952 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 637 ms 28848 KB Output is correct
9 Correct 261 ms 12924 KB Output is correct
10 Correct 254 ms 13136 KB Output is correct
11 Correct 257 ms 13388 KB Output is correct
12 Correct 314 ms 16868 KB Output is correct
13 Correct 58 ms 12120 KB Output is correct
14 Correct 1517 ms 27972 KB Output is correct
15 Correct 1044 ms 11880 KB Output is correct
16 Correct 1075 ms 11900 KB Output is correct
17 Correct 637 ms 9568 KB Output is correct
18 Correct 677 ms 9304 KB Output is correct
19 Correct 901 ms 11752 KB Output is correct
20 Correct 1418 ms 8016 KB Output is correct
21 Correct 1771 ms 9600 KB Output is correct
22 Correct 2115 ms 9012 KB Output is correct
23 Correct 613 ms 7188 KB Output is correct
24 Correct 671 ms 8792 KB Output is correct
25 Correct 851 ms 8028 KB Output is correct
26 Correct 1238 ms 11344 KB Output is correct
27 Correct 2457 ms 21580 KB Output is correct
28 Correct 1014 ms 7168 KB Output is correct
29 Correct 1043 ms 7212 KB Output is correct
30 Correct 670 ms 9368 KB Output is correct
31 Correct 1192 ms 8148 KB Output is correct
32 Correct 392 ms 9932 KB Output is correct
33 Correct 905 ms 9040 KB Output is correct