Submission #1277767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277767		longdeptrai	Lampice (COCI19_lampice)	C++20	110 / 110	1919 ms	15600 KiB

lampice

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define LongDepTrai "lampice"
#define ll long long
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) int((x).size())
#define order_set(T) tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>

inline ll add(ll a, ll b, ll mod){ a += b; if(a >= mod) a -= mod; return a; }
inline ll sub(ll a, ll b, ll mod){ a -= b; if(a < 0) a += mod; return a; }
inline ll mul(ll a, ll b, ll mod){ return ( (ll)a * b ) % mod; }

static mt19937_64 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());

const int N=5e4+9;
const int base=341;
const int mod=1e9+7;
string s;
//hash1[v]=(hash1[u]*base+(c[v]-'a')+1)%mod.
//hash2[v]=((c[v]-'a')+1+hash2[u]*Pow[1])%mod)%mod.
//hash2[u]*Pow[k-h[u]]-hash1[u]==hash2[v]*Pow[k-h[v]]-hash1[v].
ll Pow[N];
int n,sz[N],k,timer=0,del[N],res[N],h[N],tin[N],tout[N],tour[N];
unordered_map<ll,bool> cnt[N];
vi g[N];
void dfs(int u,int p){
    sz[u]=1;
    for(int x:g[u]){
        if(x==p) continue;
        if(del[x]) continue;
        dfs(x,u);
        sz[u]+=sz[x];
    }
}
int FindCentroid(int u,int p,int root){
    for(int x:g[u]){
        if(x==p) continue;
        if(del[x]) continue;
        if(sz[x]>sz[root]/2) {
            return FindCentroid(x,u,root);
        }
    }
    return u;
}
vector<pair<int,ll>> ups;
int mxUpd=0;
bool cal(int u,int p,int h,ll hash1,ll hash2,int len){
    if(h>len) return 0;
    if(p!=-1) hash1=(hash1*base+(s[u]-'a')+1)%mod;
    hash2=(((s[u]-'a')+1)*Pow[h-1]%mod+hash2)%mod;
    ll x=(hash2*Pow[len-h]%mod-hash1+mod)%mod;
    if(p==-1) cnt[h][x]=1;
    if(cnt[len-h+1].find(x)!=cnt[len-h+1].end()){
        return 1;
    }
    for(int x:g[u]){
        if(p==-1) ups.clear();
        if(x==p) continue;
        if(del[x]) continue;
        if(cal(x,u,h+1,hash1,hash2,len)){
            return 1;
        }
        if(p==-1)
        for(pair<int,ll> vy:ups){
            cnt[vy.fi][vy.se]=1;
        }
    }
    mxUpd=max(mxUpd,h);
    ups.pb({h,x});
    return 0;
}
bool solve(int k,int u){
    dfs(u,-1);
    int x=FindCentroid(u,-1,u);
    bool ans=0;
    mxUpd=0;
    ans=cal(x,-1,1,0,0,k);
    if(ans==1) return ans;
    for(int i=1;i<=mxUpd;i++) cnt[i].clear();
    mxUpd=0;
    del[x]=1;
    for(int v:g[x]){
        if(del[v]) continue;
        if(solve(k,v)==1) return 1;
    }
    return 0;
}
bool check(int k){
    for(int i=1;i<=n;i++) del[i]=0,cnt[i].clear();
    return solve(k,1);
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    if(fopen(LongDepTrai".inp","r")){
        freopen(LongDepTrai".inp","r",stdin);
        freopen(LongDepTrai".out","w",stdout);
    }

    cin>>n;
    cin>>s;
    int lenT=s.size();
    s=" "+s;
    Pow[0]=1;
    for(int i=1;i<=lenT;i++){
        Pow[i]=(Pow[i-1]*base)%mod;
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int l=1,r=(n-1)/2;
    int res=1;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(2*mid+1)){
            res=max(res,mid*2+1);
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    l=1,r=n/2;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(2*mid)){
            res=max(res,mid*2);
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout<<res;


    return 0;
}

Compilation message (stderr)

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

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