답안 #793647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
793647 2023-07-26T05:05:05 Z cig32 Palindromi (COCI22_palindromi) C++17
0 / 110
202 ms 242704 KB
#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[MAXN],neg[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];
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;
  }
}
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);
  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 lb=rb=bruh/2;
    int x=r[base]-rb;
    rb+=x,lb-=x;
    if(lb<l[base])continue;
    if(dq[base][lb-l[base]]!=dq[base][rb-l[base]])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]);
  int lb=sufpal[base].back()/2, rb=(sufpal[base].back()+1)/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){

}
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<=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'));
  }
  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() || true){
      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]);
      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]);
      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);
}
// 勿忘初衷
# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 212496 KB Output is correct
2 Correct 109 ms 212460 KB Output is correct
3 Incorrect 101 ms 212528 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 212496 KB Output is correct
2 Correct 109 ms 212460 KB Output is correct
3 Incorrect 101 ms 212528 KB Output isn't correct
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 202 ms 242704 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 212496 KB Output is correct
2 Correct 109 ms 212460 KB Output is correct
3 Incorrect 101 ms 212528 KB Output isn't correct
4 Halted 0 ms 0 KB -