Submission #793727

#	Time	Username	Problem	Language	Result	Execution time	Memory
793727		cig32	Palindromi (COCI22_palindromi)	C++17	110 / 110	648 ms	318640 KiB

Main

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MOD = 120734269;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
deque<bool>dq[MAXN];//the string itself
unordered_set<int>palin[MAXN];//set of hashes of palindromes, at most add 1 each time
deque<int32_t>sufpal[MAXN];//lengths of suffix palindromes
deque<int32_t>prepal[MAXN];//lengths of prefix palindromes
int dsu[MAXN];
int l[MAXN], r[MAXN];// Actual [l,r] ranges
int pos[2*MAXN],neg[2*MAXN];
int set_of(int u){
  if(dsu[u]==u) return u;
  return dsu[u]=set_of(dsu[u]);
}
void union_(int u,int v){
  dsu[set_of(u)]=set_of(v);
}
int n;
vector<int>ps_l[MAXN],ps_r[MAXN];
vector<int>ps2_l[MAXN],ps2_r[MAXN];
int h(int i, int l, int r) {
  if(r < 0) {
    int v = (ps_l[i][-l] - ps_l[i][-r - 1] + MOD) % MOD;
    v *= pos[-l];
    v %= MOD;
    return v;
  }
  else if(l < 0 && r >= 0) {
    int v = (ps_l[i][-l] - ps_l[i][0] + MOD) % MOD;
    v *= pos[-l];
    v %= MOD;
    int w = ps_r[i][r] * pos[-l];
    w %= MOD;
    v += w;
    v %= MOD;
    return v;
  }
  else {
    int v = (ps_r[i][r] - (l==0? 0: ps_r[i][l-1]) + MOD) % MOD;
    v *= neg[l];
    v %= MOD;
    return v;
  }
}
int h2(int i, int l, int r) {
  if(r < 0) {
    int v = (ps2_l[i][-l] - ps2_l[i][-r - 1] + MOD) % MOD;
    v *= pos[-l];
    v %= MOD;
    return v;
  }
  else if(l < 0 && r >= 0) {
    int v = (ps2_l[i][-l] - ps2_l[i][0] + MOD) % MOD;
    v *= pos[-l];
    v %= MOD;
    int w = ps2_r[i][r] * pos[-l];
    w %= MOD;
    v += w;
    v %= MOD;
    return v;
  }
  else {
    int v = (ps2_r[i][r] - (l==0? 0: ps2_r[i][l-1]) + MOD) % MOD;
    v *= neg[l];
    v %= MOD;
    return v;
  }
}
bool isp(int i, int l, int r) {
  int val=h(i,l,r);
  int val2=h2(i,l,r);
  if(l+r>=0)val2*=pos[l+r];
  else val2*=neg[-(l+r)];
  val2%=MOD;
  return val==val2;
}
void to_back(int base,bool x){
  dq[base].push_back(x);
  ps_r[base].push_back((ps_r[base][r[base]]+(1+(x==1))*pos[r[base]+1])%MOD);
  ps2_r[base].push_back((ps2_r[base][r[base]]+(1+(x==1))*neg[r[base]+1])%MOD);
  r[base]++;
  while(sufpal[base].size()){
    int lb,rb;
    int bruh=sufpal[base].back();
    sufpal[base].pop_back();
    if(bruh%2==1)lb=bruh/2,rb=bruh/2+1;
    else if(bruh%2==-1) lb=bruh/2-1,rb=bruh/2;
    else lb=rb=bruh/2;
    int x=r[base]-rb;
    rb+=x,lb-=x;
    if(lb<l[base])continue;
    //fully check whether [lb,rb] is palindrome
    if(!isp(base,lb,rb))continue;
    sufpal[base].push_back(bruh);
    break;
  }
  if(dq[base].size()>1&&dq[base][dq[base].size()-2] == dq[base].back()){
    sufpal[base].push_front(r[base] + r[base]-1);
  }
  sufpal[base].push_front(r[base] + r[base]);
  if(isp(base,l[base],r[base])) prepal[base].push_back(l[base]+r[base]);
  int bruh = sufpal[base].back();
  int lb, rb;
  if(bruh%2==1)lb=bruh/2,rb=bruh/2+1;
  else if(bruh%2==-1) lb=bruh/2-1,rb=bruh/2;
  else lb=rb=bruh/2;
  int xx=r[base]-rb;
  rb+=xx, lb-=xx;
  //[lb,rb] is maximum suffix palindrome, update palin
  int hash = h(base,lb,rb);
  if(palin[base].count(hash)) return;
  palin[base].insert(hash);
}
void to_front(int base,bool x){
  dq[base].push_front(x);
  ps_l[base].push_back((ps_l[base][-l[base]]+(1+(x==1))*neg[-l[base]+1])%MOD);
  ps2_l[base].push_back((ps2_l[base][-l[base]]+(1+(x==1))*pos[-l[base]+1])%MOD);
  l[base]--;
  while(prepal[base].size()){
    int lb,rb;
    int bruh=prepal[base].back();
    prepal[base].pop_back();
    if(bruh%2==1)lb=bruh/2,rb=bruh/2+1;
    else if(bruh%2==-1) lb=bruh/2-1,rb=bruh/2;
    else lb=rb=bruh/2;
    int x=lb-l[base];
    rb+=x,lb-=x;
    if(rb>r[base])continue;
    //fully check whether [lb,rb] is palindrome
    if(!isp(base,lb,rb))continue;
    prepal[base].push_back(bruh);
    break;
  }
  if(dq[base].size()>1&&dq[base][0] == dq[base][1]){
    prepal[base].push_front(l[base] + l[base]+1);
  }
  prepal[base].push_front(l[base] + l[base]);
  if(isp(base,l[base],r[base])) sufpal[base].push_back(l[base]+r[base]);
  int bruh = prepal[base].back();
  int lb, rb;
  if(bruh%2==1)lb=bruh/2,rb=bruh/2+1;
  else if(bruh%2==-1) lb=bruh/2-1,rb=bruh/2;
  else lb=rb=bruh/2;
  int xx=lb-l[base];
  rb+=xx, lb-=xx;
  //[lb,rb] is maximum suffix palindrome, update palin
  int hash = h(base,lb,rb);
  if(palin[base].count(hash)) return;
  palin[base].insert(hash);
}
void solve(int tc) {
  cin >>n;
  for(int i=1;i<=n;i++) {
    dsu[i]=i;
    l[i]=r[i]=0;
  }
  pos[0]=neg[0]=1;
  for(int i=1;i<=2*n;i++){
    pos[i]=(pos[i-1]*3)%MOD;
    neg[i]=(neg[i-1]*inv(3))%MOD;
  }
  for(int i=1;i<=n;i++) {
    char x;cin >> x;
    dq[i].push_back(x=='1');
    palin[i].insert(1+(x=='1'));
    sufpal[i].push_back(0);
    prepal[i].push_back(0);
    ps_l[i].push_back(1+(x=='1'));
    ps_r[i].push_back(1+(x=='1'));
    ps2_l[i].push_back(1+(x=='1'));
    ps2_r[i].push_back(1+(x=='1'));
  }
  for(int i=1;i<n;i++){
    int a,b;
    cin>>a>>b;
    a=set_of(a);
    b=set_of(b);
    if(dq[a].size()>=dq[b].size()){
      while(dq[b].size()){
        to_back(a,dq[b].front());
        dq[b].pop_front();
      }
      union_(a,b);
      dq[set_of(a)].swap(dq[a]);
      palin[set_of(a)].swap(palin[a]);
      swap(l[set_of(a)],l[a]);
      swap(r[set_of(a)],r[a]);
      sufpal[set_of(a)].swap(sufpal[a]);
      prepal[set_of(a)].swap(prepal[a]);
      ps_l[set_of(a)].swap(ps_l[a]);
      ps_r[set_of(a)].swap(ps_r[a]);
      ps2_l[set_of(a)].swap(ps2_l[a]);
      ps2_r[set_of(a)].swap(ps2_r[a]);
      cout<<palin[set_of(a)].size()<<"\n";
    }
    else{
      while(dq[a].size()){
        to_front(b,dq[a].back());
        dq[a].pop_back();
      }
      union_(a,b);
      dq[set_of(a)].swap(dq[b]);
      palin[set_of(a)].swap(palin[b]);
      swap(l[set_of(a)],l[b]);
      swap(r[set_of(a)],r[b]);
      sufpal[set_of(a)].swap(sufpal[b]);
      prepal[set_of(a)].swap(prepal[b]);
      ps_l[set_of(a)].swap(ps_l[b]);
      ps_r[set_of(a)].swap(ps_r[b]);
      ps2_l[set_of(a)].swap(ps2_l[b]);
      ps2_r[set_of(a)].swap(ps2_r[b]);
      cout<<palin[set_of(a)].size()<<"\n";
    }
    
  }




}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50