oj.uz

Submission #977658

# Submission time Handle Problem Language Result Execution time Memory
977658 2024-05-08T08:46:10 Z boyliguanhan Lampice (COCI19_lampice) C++17
0 / 110
 5000 ms 49528 KB 
#include<bits/stdc++.h>
using namespace std;
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;
}
int MD;
void calcdfs(int n,int p,int l,int d,int h){
    if(d>l||ans) return;
    if(d<=l/2)
    	ans|=mp[d][(hsh[n]-val[V[1]]*pw[d]%mod+mod)%mod];
    hsh[n]=(hsh[p]*B+val[n])%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,MD=max(MD,l-d);
    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;
    dfssz(n,0,s);
    MD=0;
    dfssz(n=rt,0,s);
    palin[n]=1;
    vis[n]=1;
    V.push_back(n);
    hsh[n]=val[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:94:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |         int mid=l+r+1>>1;
      |                 ~~~^~
lampice.cpp:104:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |         int mid=l1+r1+1>>1;
      |                 ~~~~~^~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3542 ms 44332 KB Output is correct
2 Incorrect 4901 ms 46372 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5015 ms 49528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5208 KB Output isn't correct
2 Halted 0 ms 0 KB -