#943793 (C++17) No.2606 Mirror Relay

提出ソース

結果

問題	No.2606 Mirror Relay
ユーザー	SSRS
提出日時	2024-01-12 23:36:26
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	529 ms / 2,000 ms
コード長	10,858 bytes
コンパイル時間	4,888 ms
コンパイル使用メモリ	272,956 KB
実行使用メモリ	71,668 KB
最終ジャッジ日時	2024-01-12 23:36:39
合計ジャッジ時間	11,341 ms
ジャッジサーバーID （参考情報）	judge13 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,548 KB
testcase_01	AC	2 ms 6,548 KB
testcase_02	AC	2 ms 6,548 KB
testcase_03	AC	2 ms 6,548 KB
testcase_04	AC	3 ms 6,548 KB
testcase_05	AC	3 ms 6,548 KB
testcase_06	AC	3 ms 6,548 KB
testcase_07	AC	3 ms 6,548 KB
testcase_08	AC	3 ms 6,548 KB
testcase_09	AC	3 ms 6,548 KB
testcase_10	AC	3 ms 6,548 KB
testcase_11	AC	3 ms 6,548 KB
testcase_12	AC	3 ms 6,548 KB
testcase_13	AC	3 ms 6,548 KB
testcase_14	AC	2 ms 6,548 KB
testcase_15	AC	2 ms 6,548 KB
testcase_16	AC	2 ms 6,548 KB
testcase_17	AC	2 ms 6,548 KB
testcase_18	AC	2 ms 6,548 KB
testcase_19	AC	6 ms 6,548 KB
testcase_20	AC	7 ms 6,548 KB
testcase_21	AC	5 ms 6,548 KB
testcase_22	AC	5 ms 6,548 KB
testcase_23	AC	5 ms 6,548 KB
testcase_24	AC	5 ms 6,548 KB
testcase_25	AC	5 ms 6,548 KB
testcase_26	AC	4 ms 6,548 KB
testcase_27	AC	6 ms 6,548 KB
testcase_28	AC	4 ms 6,548 KB
testcase_29	AC	3 ms 6,548 KB
testcase_30	AC	3 ms 6,548 KB
testcase_31	AC	3 ms 6,548 KB
testcase_32	AC	3 ms 6,548 KB
testcase_33	AC	3 ms 6,548 KB
testcase_34	AC	3 ms 6,548 KB
testcase_35	AC	3 ms 6,548 KB
testcase_36	AC	3 ms 6,548 KB
testcase_37	AC	3 ms 6,548 KB
testcase_38	AC	3 ms 6,548 KB
testcase_39	AC	81 ms 27,984 KB
testcase_40	AC	82 ms 27,976 KB
testcase_41	AC	82 ms 27,984 KB
testcase_42	AC	82 ms 27,992 KB
testcase_43	AC	82 ms 28,256 KB
testcase_44	AC	80 ms 27,944 KB
testcase_45	AC	82 ms 27,992 KB
testcase_46	AC	93 ms 27,988 KB
testcase_47	AC	81 ms 27,988 KB
testcase_48	AC	81 ms 27,988 KB
testcase_49	AC	208 ms 37,616 KB
testcase_50	AC	205 ms 38,740 KB
testcase_51	AC	222 ms 39,428 KB
testcase_52	AC	157 ms 35,028 KB
testcase_53	AC	210 ms 39,184 KB
testcase_54	AC	189 ms 38,028 KB
testcase_55	AC	438 ms 49,576 KB
testcase_56	AC	227 ms 38,240 KB
testcase_57	AC	173 ms 35,704 KB
testcase_58	AC	299 ms 41,528 KB
testcase_59	AC	89 ms 27,440 KB
testcase_60	AC	86 ms 27,432 KB
testcase_61	AC	79 ms 27,404 KB
testcase_62	AC	82 ms 27,408 KB
testcase_63	AC	90 ms 27,544 KB
testcase_64	AC	82 ms 26,768 KB
testcase_65	AC	88 ms 27,440 KB
testcase_66	AC	82 ms 26,764 KB
testcase_67	AC	83 ms 27,536 KB
testcase_68	AC	84 ms 27,420 KB
testcase_69	AC	529 ms 71,668 KB
testcase_70	AC	2 ms 6,548 KB
testcase_71	AC	2 ms 6,548 KB
testcase_72	AC	2 ms 6,548 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;
const long long M30 = ((long long) 1 << 30) - 1;
const long long M31 = ((long long) 1 << 31) - 1;
const long long MOD = ((long long) 1 << 61) - 1;
const long long BASE = 123456789;
unsigned long long modulo(unsigned long long x){
  unsigned long long xu = x >> 61;
  unsigned long long xd = x & MOD;
  unsigned long long res = xu + xd;
  if (res >= MOD){
    res -= MOD;
  }
  return res;
}
unsigned long long mul(unsigned long long a, unsigned long long b){
  unsigned long long au = a >> 31;
  unsigned long long ad = a & M31;
  unsigned long long bu = b >> 31;
  unsigned long long bd = b & M31;
  unsigned long long mid = au * bd + ad * bu;
  unsigned long long midu = mid >> 30;
  unsigned long long midd = mid & M30;
  return modulo(au * bu * 2 + midu + (midd << 31) + ad * bd);
}
struct rolling_hash{
  vector<unsigned long long> POW, S;
  rolling_hash(string s){
    int N = s.size();
    POW.resize(N + 1);
    POW[0] = 1;
    for (int i = 0; i < N; i++){
      POW[i + 1] = mul(POW[i], BASE);
    }
    S.resize(N + 1);
    S[N] = 0;
    for (int i = N - 1; i >= 0; i--){
      S[i] = modulo(mul(S[i + 1], BASE) + s[i]);
    }
  }
  unsigned long long get(int L, int R){
    return modulo(S[L] + MOD - mul(S[R], POW[R - L]));
  }
};
vector<int> manacher(string &S){
  int N = S.size();
  vector<int> ans(N, 0);
  int i = 0, j = 0;
  while (i < N){
    while (i >= j && i + j < N && S[i - j] == S[i + j]){
      j++;
    }
    ans[i] = j;
    int k = 1;
    while (i >= k && i + k < N && k + ans[i - k] < j){
      ans[i + k] = ans[i - k];
      k++;
    }
    i += k;
    j -= k;
  }
  return ans;
}
vector<int> suffix_array(const vector<int> &A, int mx){
  int N = A.size();
  vector<int> sum(mx + 1, 0);
  for (int i = 0; i < N; i++){
    sum[A[i] + 1]++;
  }
  for (int i = 0; i < mx; i++){
    sum[i + 1] += sum[i];
  }
  vector<bool> is_s(N);
  is_s[N - 1] = false;
  for (int i = N - 2; i >= 0; i--){
    is_s[i] = A[i] < A[i + 1] || A[i] == A[i + 1] && is_s[i + 1];
  }
  vector<int> id(N, -1);
  vector<int> pos;
  int M = 0;
  for (int i = 1; i < N; i++){
    if (is_s[i] && !is_s[i - 1]){
      id[i] = M;
      pos.push_back(i);
      M++;
    }
  }
  vector<int> sa(N);
  auto induce = [&](vector<int>& lms){
    sa = vector<int>(N, -1);
    vector<bool> used(N, false);
    vector<int> p(mx);
    vector<int> p2(mx);
    for (int i = 0; i < mx; i++){
      p[i] = sum[i + 1] - 1;
      p2[i] = sum[i];
    }
    for (int i = M - 1; i >= 0; i--){
      sa[p[A[lms[i]]]] = lms[i];
      p[A[lms[i]]]--;
      used[lms[i]] = true;
    }
    sa[p2[A[N - 1]]] = N - 1;
    p2[A[N - 1]]++;
    used[N - 1] = true;
    for (int i = 0; i < N; i++){
      if (sa[i] > 0){
        if (!is_s[sa[i] - 1] && !used[sa[i] - 1]){
          sa[p2[A[sa[i] - 1]]] = sa[i] - 1;
          p2[A[sa[i] - 1]]++;
          used[sa[i] - 1] = true;
        }
      }
    }
    for (int i = 0; i < N; i++){
      if (sa[i] != -1){
        if (id[sa[i]] != -1){
          used[sa[i]] = false;
          sa[i] = -1;
        }
      }
    }
    for (int i = 0; i < mx; i++){
      p[i] = sum[i + 1] - 1;
    }
    for (int i = N - 1; i >= 0; i--){
      if (sa[i] > 0){
        if (is_s[sa[i] - 1] && !used[sa[i] - 1]){
          sa[p[A[sa[i] - 1]]] = sa[i] - 1;
          p[A[sa[i] - 1]]--;
          used[sa[i] - 1] = true;
        }
      }
    }
  };
  induce(pos);
  if (M == 0){
    return sa;
  }
  vector<int> lms;
  for (int i = 0; i < N; i++){
    if (id[sa[i]] != -1){
      lms.push_back(sa[i]);
    }
  }
  vector<int> c(M);
  c[0] = 0;
  for (int i = 0; i < M - 1; i++){
    c[i + 1] = c[i];
    int x = lms[i];
    int y = lms[i + 1];
    bool ok = true;
    while (x < N && y < N){
      if (A[x] != A[y]){
        ok = false;
        break;
      }
      x++;
      y++;
      if (x == N || y == N){
        break;
      }
      if (id[x] != -1){
        if (id[y] == -1){
          ok = false;
        }
        break;
      }
    }
    if (x == N || y == N){
      ok = false;
    }
    if (!ok){
      c[i + 1]++;
    }
  }
  vector<int> rec(M);
  for (int i = 0; i < M; i++){
    rec[id[lms[i]]] = c[i];
  }
  vector<int> sa2 = suffix_array(rec, c[M - 1] + 1);
  vector<int> pos2(M);
  for (int i = 0; i < M; i++){
    pos2[i] = pos[sa2[i]];
  }
  induce(pos2);
  return sa;
}
vector<int> suffix_array(const string &S){
  int N = S.size();
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    A[i] = S[i];
  }
  return suffix_array(A, 256);
}
template <typename T>
vector<int> lcp_array(const T &A, vector<int> &SA){
  int N = A.size();
  vector<int> rank(N);
  for (int i = 0; i < N; i++){
    rank[SA[i]] = i;
  }
  vector<int> lcp(N - 1, 0);
  int h = 0;
  for (int i = 0; i < N; i++){
    if (rank[i] > 0){
      int prev = SA[rank[i] - 1];
      if (h > 0){
        h--;
      }
      while (i + h < N && prev + h < N){
        if (A[i + h] != A[prev + h]){
          break;
        }
        h++;
      }
      lcp[rank[i] - 1] = h;
    }
  }
  return lcp;
}
template <typename T>
struct sparse_table{
  vector<vector<T>> ST;
  sparse_table(){
  }
  sparse_table(vector<T> &A){
    int N = A.size();
    int LOG = 32 - __builtin_clz(N);
    ST = vector<vector<T>>(LOG, vector<T>(N));
    for (int i = 0; i < N; i++){
      ST[0][i] = A[i];
    }
    for (int i = 0; i < LOG - 1; i++){
      for (int j = 0; j < N - (1 << i); j++){
        ST[i + 1][j] = min(ST[i][j], ST[i][j + (1 << i)]);
      }
    }
  }
  int query(int L, int R){
    int d = 31 - __builtin_clz(R - L);
    return min(ST[d][L], ST[d][R - (1 << d)]);
  }
};
int main(){
  string S;
  cin >> S;
  int N = S.size();
  string S2;
  for (int i = 0; i < N; i++){
    S2 += S[i];
    S2 += '$';
  }
  vector<int> M = manacher(S2);
  rolling_hash RH(S);
  unordered_set<unsigned long long> hash_st;
  vector<tuple<int, int, unsigned long long>> P;
  for (int i = 0; i < N * 2; i++){
    int l = (i - M[i] + 2) / 2, r = (i + M[i] + 1) / 2;
    while (l < r){
      long long H = RH.get(l, r);
      if (hash_st.count(H) == 0){
        hash_st.insert(H);
        P.push_back(make_tuple(l, r, H));
      } else {
        break;
      }
      l++;
      r--;
    }
  }
  int cnt = P.size();
  sort(P.begin(), P.end(), [&](tuple<int, int, unsigned long long> a, tuple<int, int, unsigned long long> b){
    return get<1>(a) - get<0>(a) < get<1>(b) - get<0>(b);
  });
  vector<int> L(cnt), R(cnt);
  for (int i = 0; i < cnt; i++){
    L[i] = get<0>(P[i]);
    R[i] = get<1>(P[i]);
  }
  vector<pair<unsigned long long, int>> P2(cnt);
  for (int i = 0; i < cnt; i++){
    P2[i] = make_pair(get<2>(P[i]), i);
  }
  sort(P2.begin(), P2.end());
  auto find = [&](int l, int r){
    vector<pair<unsigned long long, int>>::iterator itr = lower_bound(P2.begin(), P2.end(), make_pair(RH.get(l, r), -1));
    if (itr == P2.end()){
      return -1;
    }
    if ((*itr).first != RH.get(l, r)){
      return -1;
    }
    return (*itr).second;
  };
  vector<int> p(cnt, -1);
  for (int i = 0; i < cnt; i++){
    if (R[i] - L[i] >= 3){
      p[i] = find(L[i] + 1, R[i] - 1);
    }
  }
  vector<int> imos(cnt, 0);
  for (int i = 0; i < N * 2; i++){
    int l = (i - M[i] + 2) / 2, r = (i + M[i] + 1) / 2;
    if (l < r){
      imos[find(l, r)]++;
    }
  }
  for (int i = cnt - 1; i >= 0; i--){
    if (p[i] >= 0){
      imos[p[i]] += imos[i];
    }
  }
  vector<int> SA = suffix_array(S);
  vector<int> rank(N);
  for (int i = 0; i < N; i++){
    rank[SA[i]] = i;
  }
  vector<int> LCP = lcp_array(S, SA);
  sparse_table<int> ST(LCP);
  auto get_lcp = [&](int a, int b){
    if (a == b){
      return N - a;
    }
    if (rank[a] > rank[b]){
      swap(a, b);
    }
    return ST.query(rank[a], rank[b]);
  };
  map<pair<int, int>, int> mp;
  for (int i = 0; i < cnt; i++){
    mp[make_pair(L[i], R[i])] = imos[i];
  }
  vector<pair<int, int>> V(cnt);
  for (int i = 0; i < cnt; i++){
    V[i] = make_pair(L[i], R[i]);
  }
  auto equal = [&](pair<int, int> A, pair<int, int> B){
    int L1 = A.first;
    int R1 = A.second;
    int L2 = B.first;
    int R2 = B.second;
    int lcp = get_lcp(L1, L2);
    return lcp >= R1 - L1 && lcp >= R2 - L2 && R1 - L1 == R2 - L2;
  };
  auto compare = [&](pair<int, int> A, pair<int, int> B){
    int L1 = A.first;
    int R1 = A.second;
    int L2 = B.first;
    int R2 = B.second;
    int lcp = get_lcp(L1, L2);
    if (R1 - L1 <= lcp || R2 - L2 <= lcp){
      return R1 - L1 < R2 - L2;
    } else {
      return S[L1 + lcp] < S[L2 + lcp];
    }
  };
  sort(V.begin(), V.end(), compare);
  auto lca = [&](pair<int, int> A, pair<int, int> B){
    int L1 = A.first;
    int R1 = A.second;
    int L2 = B.first;
    int R2 = B.second;
    int lcp = get_lcp(L1, L2);
    lcp = min({lcp, R1 - L1, R2 - L2});
    return make_pair(L1, L1 + lcp);
  };
  auto depth = [&](pair<int, int> A){
    return A.second - A.first;
  };
  stack<pair<int, int>> st;
  st.push(V[0]);
  vector<pair<pair<int, int>, pair<int, int>>> edges;
  for (int i = 1; i < cnt; i++){
    pair<int, int> v = lca(V[i - 1], V[i]);
    while (!st.empty()){
      pair<int, int> w = st.top();
      if (depth(v) < depth(w)){
        st.pop();
        pair<int, int> pr = v;
        if (!st.empty()){
          if (depth(pr) < depth(st.top())){
            pr = st.top();
          }
        }
        if (!equal(pr, w)){
          edges.push_back(make_pair(pr, w));
        }
      } else {
        break;
      }
    }
    if (st.empty()){
      st.push(v);
    } else if (!equal(st.top(), v)){
      st.push(v);
    }
    if (!equal(st.top(), V[i])){
      st.push(V[i]);
    }
  }
  while (st.size() >= 2){
    pair<int, int> v = st.top();
    st.pop();
    pair<int, int> w = st.top();
    edges.push_back(make_pair(w, v));
  }
  int E = edges.size();
  vector<pair<int, int>> V2 = V;
  for (int i = 0; i < E; i++){
    V2.push_back(edges[i].first);
    V2.push_back(edges[i].second);
  }
  sort(V2.begin(), V2.end(), compare);
  V2.erase(unique(V2.begin(), V2.end(), equal), V2.end());
  int cnt2 = V2.size();
  vector<pair<int, int>> edges2(E);
  for (int i = 0; i < E; i++){
    edges2[i].first = lower_bound(V2.begin(), V2.end(), edges[i].first, compare) - V2.begin();
    edges2[i].second = lower_bound(V2.begin(), V2.end(), edges[i].second, compare) - V2.begin();
  }
  vector<int> pr(cnt2, -1);
  for (int i = 0; i < E; i++){
    pr[edges2[i].second] = edges2[i].first;
  }
  vector<long long> score(cnt2, 0);
  for (auto X : mp){
    int pos = lower_bound(V2.begin(), V2.end(), X.first, compare) - V2.begin();
    score[pos] += (long long) X.second * (X.first.second - X.first.first);
  }
  vector<long long> dp(cnt2, 0);
  for (int i = cnt2 - 1; i >= 0; i--){
    dp[i] += score[i];
    if (pr[i] != -1){
      dp[pr[i]] = max(dp[pr[i]], dp[i]);
    }
  }
  long long ans = *max_element(dp.begin(), dp.end());
  cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード