Codeforces Round #763 DIV2 E問題 - Middle Duplication

Source

Codeforces Round #763 DIV2 E問題 (2750pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20211229-1）のコード

C++に変換後のコードはこちら

//no-unlocked
int N, K, A[4d5+2], B[];
int mm, aa[], bb[], dup[];
graph g;
HLD hld;
HLD_fenwick<int> f;
char S[], res[]; int ress, arr[], sz, doit[];

void dfs(int n){
  if(n==-1) return;
  dfs(A[n]); arr[sz++] = n; dfs(B[n]);
}

int getdep(int n){
  int k;
  return bsearch_min[int,x,0,N+1][
    k = hld.up(n,x);
  ](k==-1 || dup[k]);
}

{
  int i, j, k, m;
  rd(N,K,S,(A--,B--)(N));
  rep(i,N) if(A[i] >= 0) arrInsert(mm, mm, aa, i, bb, A[i]);
  rep(i,N) if(B[i] >= 0) arrInsert(mm, mm, aa, i, bb, B[i]);
  g.setEdge(N,mm,aa,bb);
  hld.init(g);
  f.init(&hld);

  dfs(0);
  rrep(i,N-1){
    if(S[arr[i]] < S[arr[i+1]]) doit[i] = 1, continue;
    if(S[arr[i]] == S[arr[i+1]]) doit[i] = doit[i+1], continue;
  }

  rep(i,N) if(!dup[arr[i]]){
    if((doit[i] && f.get(0,arr[i])==0)){
      k = getdep(arr[i]);
      if(k <= K){
        K -= k;
        j = arr[i];
        rep(k){
          dup[j] = 1;
          j = hld.up(j);
        }
      }
    } else {
      f.add(arr[i], 1);
    }
  }

  rep(i,N){
    res[ress++] = S[arr[i]];
    if(dup[arr[i]]) res[ress++] = S[arr[i]];
  }

  wt(res);
}

Current time: 2024年05月19日04時45分07秒
Last modified: 2021年12月29日20時58分28秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF763 CF_DIV2_E
トップページに戻る

Logged in as: unknown user (not login)