oj.uz

Submission #793707

# Submission time Handle Problem Language Result Execution time Memory
793707 2023-07-26T05:46:53 Z cig32 Palindromi (COCI22_palindromi) C++17
60 / 110
 842 ms 524288 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;
  }
}
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 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
    int val=h(base,lb,rb);
    int val2=h2(base,lb,rb);
    if(lb+rb>=0)val2*=pos[lb+rb];
    else val2*=neg[-(lb+rb)];
    val2%=MOD;
    if(val!=val2)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<=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() || 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]);
      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 101 ms 217072 KB Output is correct
2 Correct 104 ms 217200 KB Output is correct
3 Correct 102 ms 217240 KB Output is correct
4 Correct 103 ms 217256 KB Output is correct
5 Correct 103 ms 217192 KB Output is correct
6 Correct 104 ms 217240 KB Output is correct
7 Correct 109 ms 217308 KB Output is correct
8 Correct 106 ms 217344 KB Output is correct
9 Correct 118 ms 217112 KB Output is correct
10 Correct 98 ms 217464 KB Output is correct
11 Correct 97 ms 217444 KB Output is correct
12 Correct 97 ms 217228 KB Output is correct
13 Correct 103 ms 217208 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 217072 KB Output is correct
2 Correct 104 ms 217200 KB Output is correct
3 Correct 102 ms 217240 KB Output is correct
4 Correct 103 ms 217256 KB Output is correct
5 Correct 103 ms 217192 KB Output is correct
6 Correct 104 ms 217240 KB Output is correct
7 Correct 109 ms 217308 KB Output is correct
8 Correct 106 ms 217344 KB Output is correct
9 Correct 118 ms 217112 KB Output is correct
10 Correct 98 ms 217464 KB Output is correct
11 Correct 97 ms 217444 KB Output is correct
12 Correct 97 ms 217228 KB Output is correct
13 Correct 103 ms 217208 KB Output is correct
14 Correct 104 ms 217172 KB Output is correct
15 Correct 116 ms 221384 KB Output is correct
16 Correct 109 ms 219164 KB Output is correct
17 Correct 119 ms 219144 KB Output is correct
18 Correct 117 ms 219604 KB Output is correct
19 Correct 154 ms 231856 KB Output is correct
20 Correct 145 ms 225500 KB Output is correct
21 Correct 110 ms 217544 KB Output is correct
22 Correct 120 ms 217440 KB Output is correct
23 Correct 169 ms 245428 KB Output is correct
24 Correct 189 ms 231800 KB Output is correct
25 Correct 110 ms 217876 KB Output is correct
26 Correct 115 ms 217800 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 249900 KB Output is correct
2 Correct 283 ms 255144 KB Output is correct
3 Correct 245 ms 250312 KB Output is correct
4 Correct 273 ms 255596 KB Output is correct
5 Correct 250 ms 252200 KB Output is correct
6 Correct 267 ms 254500 KB Output is correct
7 Correct 254 ms 252052 KB Output is correct
8 Correct 250 ms 253984 KB Output is correct

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 217072 KB Output is correct
2 Correct 104 ms 217200 KB Output is correct
3 Correct 102 ms 217240 KB Output is correct
4 Correct 103 ms 217256 KB Output is correct
5 Correct 103 ms 217192 KB Output is correct
6 Correct 104 ms 217240 KB Output is correct
7 Correct 109 ms 217308 KB Output is correct
8 Correct 106 ms 217344 KB Output is correct
9 Correct 118 ms 217112 KB Output is correct
10 Correct 98 ms 217464 KB Output is correct
11 Correct 97 ms 217444 KB Output is correct
12 Correct 97 ms 217228 KB Output is correct
13 Correct 103 ms 217208 KB Output is correct
14 Correct 104 ms 217172 KB Output is correct
15 Correct 116 ms 221384 KB Output is correct
16 Correct 109 ms 219164 KB Output is correct
17 Correct 119 ms 219144 KB Output is correct
18 Correct 117 ms 219604 KB Output is correct
19 Correct 154 ms 231856 KB Output is correct
20 Correct 145 ms 225500 KB Output is correct
21 Correct 110 ms 217544 KB Output is correct
22 Correct 120 ms 217440 KB Output is correct
23 Correct 169 ms 245428 KB Output is correct
24 Correct 189 ms 231800 KB Output is correct
25 Correct 110 ms 217876 KB Output is correct
26 Correct 115 ms 217800 KB Output is correct
27 Correct 247 ms 249900 KB Output is correct
28 Correct 283 ms 255144 KB Output is correct
29 Correct 245 ms 250312 KB Output is correct
30 Correct 273 ms 255596 KB Output is correct
31 Correct 250 ms 252200 KB Output is correct
32 Correct 267 ms 254500 KB Output is correct
33 Correct 254 ms 252052 KB Output is correct
34 Correct 250 ms 253984 KB Output is correct
35 Correct 116 ms 217156 KB Output is correct
36 Runtime error 842 ms 524288 KB Execution killed with signal 9
37 Halted 0 ms 0 KB -