Submission #895883

#	Time	Username	Problem	Language	Result	Execution time	Memory
895883		now_or_never	Lampice (COCI19_lampice)	C++14	0 / 110	5045 ms	14172 KiB

lampice

//Name: Nguyen Quang Huy
//Time: 2023-2024
#include <bits/stdc++.h>
#define Foru(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define se second
#define fi first
#define nl cout << "\n";
#define pi pair<int,int>
#define bit(x, k) (1ll&((x)>>(k)))
//#define sz size
#define io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ms(a,i) memset(a,i,sizeof(a))
#define pb(x) push_back(x)
#define epb(x,y) emplace_back({x,y})
#define all(x) (x).begin(), (x).end()
#define hr cout << "-----------------------------------------------\n";

typedef long long ll;

using namespace std;
const ll mod=1e9+7;
const int inf=0x3f3f3f3f;
const long long base=311;
const int maxn=5e4+7;

template<class T> T mi(T a, T b){return (a<=b)?a:b;}
template<class T> T ma(T a, T b){return (a>=b)?a:b;}
template<class T> void Unique(vector<T> &v){sort(all(v));v.erase(unique(all(v)), v.end());}

int n;
vector<int> g[maxn];
int sz[maxn], mxd=1, Len, ans, cc;
char a[maxn];
ll pw[maxn];
bool del[maxn], found;
unordered_map<ll,bool> mp[maxn];

void ioFile(string str){
    freopen((str+".in").c_str(),"r",stdin);
    freopen((str+".out").c_str(),"w",stdout);
}

void inp(){
    cin >> n;
    Foru(i,1,n)cin >> a[i];
    Foru(i,1,n-1){
        int u,v;cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    pw[0]=1;
    Foru(i,1,maxn) pw[i]=(1ll*pw[i-1]*base)%mod;
}

void dfsBase(int u,int p){
    sz[u]=1;
    for(int v:g[u])if(v!=p&&!del[v]){
        dfsBase(v,u);
        sz[u]+=sz[v];
    }
}

int centroid(int u, int p, int d){
    for(int v:g[u])if(v!=p&&sz[v]>d&&!del[v]){
        return centroid(v,u,d);
    }
    return u;
}

bool dfs(int u, int p, int h, ll hd, ll hu, bool t){
    hd=(hd*1ll*base+(a[u]-'a'+1))&mod;
    hu=(hu+pw[h-1]*1ll*(a[u]-'a'+1))%mod;
    ll x=(hu*1ll*pw[Len-h]-hd+mod)%mod;
    if(t){
        if(h+1==Len&&((hu*1ll*base+(a[cc]-'a'+1))%mod==hd)){
            return true;
        }
        if(Len>h&&mp[Len-h-1].find(x)!=mp[Len-h-1].end()){
            return true;
        }
    } else {mp[h][x]=true;}
    if(Len>h){
        for(int v:g[u])if(v!=p&&!del[v]){
            mxd=max(mxd,h+1);
            if(dfs(v,u,h+1,hd,hu,t))return true;
        }
    }
    return false;
}

bool cd(int u=1){
    dfsBase(u,0);
    int r=centroid(u,0,sz[u]/2);
    cc=r;
    del[r]=true;
    mxd=1;

    for(int v:g[r])if(!del[v]){
        if(dfs(v,0,1,(a[r]-'a'+1),0,true))return true;
        if(dfs(v,0,1,(a[r]-'a'+1),0,false))return true;
    }

    Foru(i,0,mxd)mp[i].clear();

    for(int v:g[r])if(!del[v]){
        if(cd(v))return true;
    }
    return false;
}

bool ok(int len){
    Foru(i,0,n)mp[i].clear();
    ms(del,false);
    found=false;
    Len=len;
    return cd();
}


void solve(){
    vector<int> le,chan;
    le.pb(1);chan.pb(2);
    Foru(i,1,n){
        if(i&1)le.pb(i);
        else chan.pb(i);
    }
    int l=1,r=le.size()-1,mid;
    while(l<r){
        mid=(l+r)/2;
        if(ok(le[mid]))l=mid;
        else r=mid-1;
    }
    ans=le[l];
    l=1,r=chan.size()-1;
    while(l<r){
        mid=(l+r)/2;
        if(ok(chan[mid]))l=mid;
        else r=mid-1;
    }
    cout << max(chan[l],ans);
}

int main(){
	io();
    inp();
    solve();

	return 0;
}

Compilation message (stderr)

lampice.cpp: In function 'void ioFile(std::string)':
lampice.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen((str+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen((str+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp: In function 'void inp()':
lampice.cpp:53:25: warning: iteration 50006 invokes undefined behavior [-Waggressive-loop-optimizations]
   53 |     Foru(i,1,maxn) pw[i]=(1ll*pw[i-1]*base)%mod;
      |                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
lampice.cpp:4:36: note: within this loop
    4 | #define Foru(i,a,b) for(int i=(a);i<=(b);++i)
      |                                    ^
lampice.cpp:53:5: note: in expansion of macro 'Foru'
   53 |     Foru(i,1,maxn) pw[i]=(1ll*pw[i-1]*base)%mod;
      |     ^~~~

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