oj.uz

Submission #793727

# Submission time Handle Problem Language Result Execution time Memory
793727 2023-07-26T06:00:19 Z cig32 Palindromi (COCI22_palindromi) C++17
110 / 110
 648 ms 318640 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[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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 217160 KB Output is correct
2 Correct 127 ms 217168 KB Output is correct
3 Correct 105 ms 217232 KB Output is correct
4 Correct 119 ms 217236 KB Output is correct
5 Correct 121 ms 217232 KB Output is correct
6 Correct 111 ms 217216 KB Output is correct
7 Correct 108 ms 217204 KB Output is correct
8 Correct 101 ms 217164 KB Output is correct
9 Correct 111 ms 217152 KB Output is correct
10 Correct 121 ms 217220 KB Output is correct
11 Correct 134 ms 217216 KB Output is correct
12 Correct 108 ms 217252 KB Output is correct
13 Correct 115 ms 217164 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 217160 KB Output is correct
2 Correct 127 ms 217168 KB Output is correct
3 Correct 105 ms 217232 KB Output is correct
4 Correct 119 ms 217236 KB Output is correct
5 Correct 121 ms 217232 KB Output is correct
6 Correct 111 ms 217216 KB Output is correct
7 Correct 108 ms 217204 KB Output is correct
8 Correct 101 ms 217164 KB Output is correct
9 Correct 111 ms 217152 KB Output is correct
10 Correct 121 ms 217220 KB Output is correct
11 Correct 134 ms 217216 KB Output is correct
12 Correct 108 ms 217252 KB Output is correct
13 Correct 115 ms 217164 KB Output is correct
14 Correct 114 ms 217068 KB Output is correct
15 Correct 119 ms 217748 KB Output is correct
16 Correct 115 ms 217720 KB Output is correct
17 Correct 132 ms 217744 KB Output is correct
18 Correct 118 ms 217688 KB Output is correct
19 Correct 120 ms 217544 KB Output is correct
20 Correct 122 ms 217536 KB Output is correct
21 Correct 127 ms 217468 KB Output is correct
22 Correct 107 ms 217496 KB Output is correct
23 Correct 106 ms 217492 KB Output is correct
24 Correct 116 ms 217452 KB Output is correct
25 Correct 117 ms 217948 KB Output is correct
26 Correct 127 ms 217780 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 249868 KB Output is correct
2 Correct 261 ms 254692 KB Output is correct
3 Correct 252 ms 249476 KB Output is correct
4 Correct 260 ms 255072 KB Output is correct
5 Correct 256 ms 251364 KB Output is correct
6 Correct 242 ms 254020 KB Output is correct
7 Correct 260 ms 251168 KB Output is correct
8 Correct 291 ms 253552 KB Output is correct

Subtask #4
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 217160 KB Output is correct
2 Correct 127 ms 217168 KB Output is correct
3 Correct 105 ms 217232 KB Output is correct
4 Correct 119 ms 217236 KB Output is correct
5 Correct 121 ms 217232 KB Output is correct
6 Correct 111 ms 217216 KB Output is correct
7 Correct 108 ms 217204 KB Output is correct
8 Correct 101 ms 217164 KB Output is correct
9 Correct 111 ms 217152 KB Output is correct
10 Correct 121 ms 217220 KB Output is correct
11 Correct 134 ms 217216 KB Output is correct
12 Correct 108 ms 217252 KB Output is correct
13 Correct 115 ms 217164 KB Output is correct
14 Correct 114 ms 217068 KB Output is correct
15 Correct 119 ms 217748 KB Output is correct
16 Correct 115 ms 217720 KB Output is correct
17 Correct 132 ms 217744 KB Output is correct
18 Correct 118 ms 217688 KB Output is correct
19 Correct 120 ms 217544 KB Output is correct
20 Correct 122 ms 217536 KB Output is correct
21 Correct 127 ms 217468 KB Output is correct
22 Correct 107 ms 217496 KB Output is correct
23 Correct 106 ms 217492 KB Output is correct
24 Correct 116 ms 217452 KB Output is correct
25 Correct 117 ms 217948 KB Output is correct
26 Correct 127 ms 217780 KB Output is correct
27 Correct 242 ms 249868 KB Output is correct
28 Correct 261 ms 254692 KB Output is correct
29 Correct 252 ms 249476 KB Output is correct
30 Correct 260 ms 255072 KB Output is correct
31 Correct 256 ms 251364 KB Output is correct
32 Correct 242 ms 254020 KB Output is correct
33 Correct 260 ms 251168 KB Output is correct
34 Correct 291 ms 253552 KB Output is correct
35 Correct 107 ms 217120 KB Output is correct
36 Correct 648 ms 277928 KB Output is correct
37 Correct 611 ms 269540 KB Output is correct
38 Correct 625 ms 279392 KB Output is correct
39 Correct 562 ms 273068 KB Output is correct
40 Correct 365 ms 254888 KB Output is correct
41 Correct 341 ms 252000 KB Output is correct
42 Correct 286 ms 254480 KB Output is correct
43 Correct 267 ms 251852 KB Output is correct
44 Correct 247 ms 254208 KB Output is correct
45 Correct 247 ms 251524 KB Output is correct
46 Correct 501 ms 318640 KB Output is correct
47 Correct 455 ms 289908 KB Output is correct