Submission #1116645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116645		son2008	Lampice (COCI19_lampice)	C++14	42 / 110	5045 ms	175912 KiB

lampice

#include<bits/stdc++.h>
using namespace std;
#define task "noel"
#define ii pair<int,int>
#define fi first
#define se second
#define int long long
#define ll long long
#define ld double
#define mp make_pair
#define lg2 30
#define iii pair<int,ii>
#define iiii pair<ii,ii>
#define fii fi.fi
#define fis fi.se3
#define sfi se.fi
#define see se.se
#define base 29
int dx[]={0LL,0LL,1,-1,1,1,-1,-1};
int dy[]={1,-1,0LL,0LL,1,-1,1,-1};
const int maxn=5e4+1;
const int mod=1e9+7;
int h[maxn],n;
char s[maxn];
vector<int>a[maxn];
void dfs(int u,int cha)
{
    for(int v:a[u])
    {
        if(v==cha)continue;
        h[v]=h[u]+1;
        dfs(v,u);
    }
}
namespace sub2
{
    int h[50068],p[50068],hr[50068];
    int getl(int l,int r){
	return (h[r]-h[l-1]*p[r-l+1]%mod+mod)%mod;
    }
    int getr(int i, int j) {
    return (hr[i] - hr[j+1] * p[j-i+1]%mod+mod)%mod;
    }
    bool check(int i,int j){
    return (getl(i,j)==getr(i,j));
    }
    void solve(void)
    {
        p[0]=1;
	for(int i=1;i<=n;i++){
		h[i]=(h[i-1]*base+s[i]-'a'+1)%mod;
        p[i]=(p[i-1]*base)%mod;
	}
	for(int i=n;i>=1;i--)
	hr[i]=(hr[i+1]*base+s[i]-'a'+1)%mod;
	int ans=0;
	for(int i=1;i<=n;i++){
        int l=0,r=min(n-i,i);
        while(l<=r){
            int mid=(l+r)/2;
            if(check(i-mid+1,i+mid)){
                ans=max(ans,mid*2);
                l=mid+1;
            }
            else
                r=mid-1;
        }
        l=0,r=min(i-1,n-i);
        while(l<=r){
            int mid=(l+r)/2;
            if(check(i-mid,i+mid)){
                ans=max(ans,mid*2+1);
                l=mid+1;
            }
            else
                r=mid-1;
        }
	}
	cout<<ans;
    }
}
namespace sub1
{
    int ans=1,goc;
    int D_odd[maxn],D_even[maxn];
    void Calc_D_odd(string S) {
    int N=S.size();
    S=" "+S;
    int L = 1;
    int R = 0;
    for(int i = 1 ; i <= N ; i++) {
        if(i > R) D_odd[i] = 0;
        else D_odd[i] = min(R - i, D_odd[L + (R - i)]);
        while(i - D_odd[i] - 1 > 0 && i + D_odd[i] + 1 <= N && S[i - D_odd[i] - 1] == S[i + D_odd[i] + 1]) {
            D_odd[i]++;
        }

        if(i + D_odd[i] > R) {
            R = i + D_odd[i];
            L = i - D_odd[i];
        }
    }
}

void Calc_D_even(string S) {
    int N=S.size();
    S=" "+S;
    int L = 1;
    int R = 0;
    for(int i = 1 ; i < N ; i++) {
        int j = i + 1;
        if(j > R) D_even[i] = 0;
        else D_even[i] = min(R - j + 1, D_even[L + (R - j)]);
        while(i - D_even[i] > 0 && j + D_even[i] <= N && S[i - D_even[i]] == S[j + D_even[i]]) {
            D_even[i]++;
        }
        if(i + D_even[i] > R) {
            R = i + D_even[i];
            L = j - D_even[i];
        }
    }
}
    void manacher(string S)
    {
        Calc_D_even(S);
        Calc_D_odd(S);
        int N=S.size();
        for(int i=1;i<N;i++)
        {
            ans=max({ans,D_even[i]*2,D_odd[i]*2+1});
        }
    }
    void dfs(int u,int cha,string tmp)
    {
        tmp+=s[u];
        if(a[u].size()==1&&u!=goc)
            manacher(tmp);
        for(int v:a[u])
        {
            if(v==cha)continue;
            dfs(v,u,tmp);
        }
    }
    void solve(void)
    {
        for(int i=1;i<=n;i++)
        {
            goc=i;
            dfs(i,-1,"");
        }
        cout<<ans;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(task".inp","r")){
    freopen(task".inp","r",stdin);
    freopen(task".out","w",stdout);}
    cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(1,-1);
    if(h[n]==n-1)sub2::solve();
    else sub1::solve();
    cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ;
}

Compilation message (stderr)

lampice.cpp: In function 'int main()':
lampice.cpp:158:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     freopen(task".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:159:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |     freopen(task".out","w",stdout);}
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 31
• Subtask 4: 0 / 37