oj.uz

Submission #403266

# Submission time Handle Problem Language Result Execution time Memory
403266 2021-05-13T00:57:06 Z rama_pang Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 1456 KB 
#include <bits/stdc++.h>
using namespace std;

class Trie {
 public:
  vector<int> sl; // suffix link
  vector<int> len; // length of current node
  vector<array<int, 26>> go; // transition

  int NewNode() {
    sl.emplace_back(0);
    len.emplace_back(0);
    go.emplace_back(array<int, 26>());
    return int(sl.size()) - 1;
  }

  void Insert(string s) {
    int u = 0;
    for (auto c : s) {
      if (!go[u][c - 'a']) {
        int n = NewNode();
        go[u][c - 'a'] = n;
      }
      u = go[u][c - 'a'];
    }
  }

  void Build() {
    for (queue<int> q({0}); !q.empty(); q.pop()) {
      int u = q.front();
      for (int i = 0; i < 26; i++) {
        int v = go[u][i]; go[u][i] = 0;
        if (v) {
          sl[v] = go[sl[u]][i];
          len[v] = len[u] + 1;
          go[u][i] = v;
          q.emplace(v);
        } else {
          go[u][i] = go[sl[u]][i];
        }
      }
    }
  }

  Trie(string str) {
    NewNode(); // initialize root
    Insert(str);
    Build();
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  string S, T;
  cin >> S >> T;

  const auto Solve = [&]() -> array<int, 3> {
    int N = S.size();
    int M = T.size();

    array<int, 3> ans = {0, 0, 0};

    vector<int> lcs(M); // lcs[t] = longest common suffix of S[0...s], T[0...t]
    for (int s = 0; s < N; s++) {
      for (int t = M - 1; t >= 0; t--) {
        if (S[s] == T[t]) {
          lcs[t] = 1 +  (t > 0 ? lcs[t - 1] : 0);
        } else {
          lcs[t] = 0;
        }
      }

      vector<int> dp(M); // dp[t] = longest prefix of S[s+1...N] which is suffix of T[0...t]

      string str;
      for (int i = s + 1; i < N; i++) {
        str.push_back(S[i]);
      }

      Trie trie(str);
      for (int t = 0, i = 0; t < M; t++) {
        i = trie.go[i][T[t] - 'a'];
        dp[t] = max(dp[t], trie.len[i]);
      }
      for (int t = M - 2; t >= 0; t--) {
        dp[t] = max(dp[t], dp[t + 1] - 1);
      }

      for (int t = 0; t < M; t++) if (lcs[t] > 0) {
        int k = lcs[t] + (t < lcs[t] ? 0 : dp[t - lcs[t]]);
        ans = max(ans, {k, s - lcs[t] + 1, t - k + 1});
      }
    }

    return ans;
  };

  auto ans1 = Solve();
  reverse(begin(T), end(T));
  auto ans2 = Solve();
  ans2[2] = int(T.size()) - ans2[2] - ans2[0];
  auto ans = max(ans1, ans2);

  cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << '\n';
  return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 312 KB Output is correct
5 Correct 3 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 312 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 29 ms 332 KB Output is correct
7 Correct 29 ms 432 KB Output is correct
8 Correct 28 ms 432 KB Output is correct
9 Correct 27 ms 428 KB Output is correct
10 Correct 30 ms 432 KB Output is correct
11 Correct 29 ms 308 KB Output is correct
12 Correct 28 ms 432 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 3 ms 312 KB Output is correct
5 Correct 3 ms 332 KB Output is correct
6 Correct 29 ms 332 KB Output is correct
7 Correct 29 ms 432 KB Output is correct
8 Correct 28 ms 432 KB Output is correct
9 Correct 27 ms 428 KB Output is correct
10 Correct 30 ms 432 KB Output is correct
11 Correct 29 ms 308 KB Output is correct
12 Correct 28 ms 432 KB Output is correct
13 Execution timed out 1596 ms 1456 KB Time limit exceeded
14 Halted 0 ms 0 KB -