Submission #299762

#	Time	Username	Problem	Language	Result	Execution time	Memory
299762		LifeHappen__	Lampice (COCI19_lampice)	C++14	110 / 110	4882 ms	13300 KiB

lampice

#include<bits/stdc++.h>

using namespace std;

#define FOR(a,b,c) for(int a=b, __c=c; a<=__c; ++a)
#define FORD(a,b,c) for(int a=b, __c=c; a>=__c; --a)
#define forv(a,b) for(auto &a:b)

#define ii pair<int,int>
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define reset(f,x) memset(f,x,sizeof(f))
#define pb push_back
#define eb emplace_back
#define fasty ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define gg exit(0);

#define bit(x,i) (x>>(i-1)&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))

using ull=unsigned long long;

const int N=5e4+5;
const int base=19937;
int n;
char a[N];
vector<int> ad[N];
ull pw[N];
int dd[N],sz[N],cnt;
int dep[N];
ull hash_up[N], hash_down[N];
int pd[N][18];
vector<pair<ull,int>> has[N];
vector<int> node;
bool ok=false;

void dfs(int u,int par){
   sz[u]=1; cnt++;
   forv(v,ad[u]) if(!dd[v] && v!=par) dfs(v,u), sz[u]+=sz[v];
}
int ftr(int u,int par){
   forv(v,ad[u]) if(!dd[v] && v!=par && sz[v]>cnt/2) return ftr(v,u);
   return u;
}
void prep(int u,int par){
   node.pb(u);
   FOR(i,1,17) pd[u][i]=pd[pd[u][i-1]][i-1];
   hash_up[u]=hash_up[par]+pw[dep[u]-1]*(a[u]-'a'+1);
   hash_down[u]=hash_down[par]*base+(a[u]-'a'+1);
   has[dep[u]].pb(make_pair(hash_down[u],u));
   forv(v,ad[u]) if(v!=par && !dd[v]){
      pd[v][0]=u;
      dep[v]=dep[u]+1;
      prep(v,u);
   }
}
int jump(int u,int dep){
   FORD(i,17,0) if(dep>>i&1) u=pd[u][i];
   return u;
}
int lca(int u,int v){
   if(dep[u]<dep[v]) swap(u,v);
   int _=dep[u]-dep[v];
   u=jump(u,_);
   if(u==v) return u;
   FORD(i,17,0) if(pd[u][i]!=pd[v][i]) u=pd[u][i], v=pd[v][i];
   return pd[u][0];
}
ull que(int u,int v){
   return hash_down[u]-hash_down[pd[v][0]]*pw[dep[u]-dep[v]+1];
}
void solve(int u,int L){
   if(ok) return;
   node.clear();
   dep[u]=1;
   pd[u][0]=0;
   hash_up[u]=hash_down[u]=0;
   prep(u,u);
   FOR(i,1,n) if(has[i].size()){
      sort(all(has[i]));
   } else break;
   forv(v,node){
      if(ok) break;
      int len=L-dep[v]+1;
      if(len>dep[v] || len<1) continue;
      int x=jump(v,len-1);
      if(hash_down[x]!=hash_up[x]) continue;
      ull C=que(v,x);
      auto p=lower_bound(all(has[len]), pair<ull,int>(C,-1))-begin(has[len]);
      if(p==(int)has[len].size() || has[len][p].fi!=C) continue;
      while(p<(int)has[len].size()){
         if(has[len][p].fi != C) break;
         int _=has[len][p].se;
         if(lca(v,_)==u){
            ok=1;
            break;
         }
         else p++;
      }
   }
   FOR(i,1,n) if((int)has[i].size()) has[i].clear(); else break;
}

void ctr(int u,int L){
   if(ok) return;
   cnt=0;
   dfs(u,0);
   int C=ftr(u,0);
   dd[C]=1;
   solve(C,L);
   forv(v,ad[C]) if(!dd[v]) ctr(v,L);
}
bool chk(int len,int odd){
   len=len*2+odd;
   ok=false;
   FOR(i,1,n) dd[i]=0;
   ctr(1,len);
   return ok;
}

int32_t main(){
   fasty;

   #define task "lampice"
   if(fopen(task".in","r")) freopen(task".in","r",stdin);

   cin>>n;
   FOR(i,1,n) cin>>a[i];
   FOR(i,1,n-1){
      int u,v;
      cin>>u>>v;
      ad[u].pb(v); ad[v].pb(u);
   }

   pw[0]=1;
   FOR(i,1,n) pw[i]=pw[i-1]*base;

   int l=0, r=n/2, rett=0;
   while(l<=r){
      int m=l+(r-l)/2;
      if(chk(m,1)) rett=m, l=m+1;
      else r=m-1;
   }
   int ans=rett*2+1;

   l=1, r=n/2, rett=0;
   while(l<=r){
      int m=l+(r-l)/2;
      if(chk(m,0)) rett=m, l=m+1;
      else r=m-1;
   }

   ans=max(ans,rett*2);
   cout<<ans<<'\n';
}

Compilation message (stderr)

lampice.cpp: In function 'int32_t main()':
lampice.cpp:127:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  127 |    if(fopen(task".in","r")) freopen(task".in","r",stdin);
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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