Submission #1189724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189724		Muaath_5	Hieroglyphs (IOI24_hieroglyphs)	C++20	3 / 100	19 ms	8008 KiB

hieroglyphs

#include <bits/stdc++.h>
#include "hieroglyphs.h"
using namespace std;

int N, M;

vector<int> lcs(vector<int> s, vector<int> t) {
  int P_LCS[N+2][M+2] = {};
  int S_LCS[N+2][M+2] = {};

  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= M; j++) {
      P_LCS[i][j] = max({P_LCS[i-1][j], P_LCS[i][j-1], P_LCS[i-1][j-1] + (s[i-1] == t[j-1])});
    }
  }

  for (int i = N; i >= 1; i--) {
    for (int j = M; j >= 1; j--) {
      S_LCS[i][j] = max({S_LCS[i+1][j], S_LCS[i][j+1], S_LCS[i+1][j+1] + (s[i-1] == t[j-1])});
    }
  }

  vector<int> res;
  int x = N, y = M;
  while (x > 0 && y > 0) {
    if (max(P_LCS[x-1][y], P_LCS[x][y-1]) == P_LCS[x][y]-1) {
      res.push_back(s[x-1]);
      x--, y--;
    } else if (P_LCS[x][y] == P_LCS[x-1][y]) {
      x--;
    } else {
      y--;
    }
  }
  reverse(res.begin(), res.end());

  if (res.size() == 0) return {};

  bool has_two_lcs = false;
  int idx = 0;
  for (int i = 1; i <= N; i++) {

    if (s[i-1] == res[idx]) {


      int mx = 0;
      for (int j = 1; j < M; j++) {
        mx = max(mx, P_LCS[i-1][j] + S_LCS[i+1][j+1]);
      }
      if (mx == P_LCS[N][M]) {
        has_two_lcs = true;
        break;
      }
      
      idx++;
    }

  }
  if (has_two_lcs) return {-1};
  return res;
}


// A, B
// LCS(A, B) = S
// 



// i
// LCS1(i-1, j) + LCS2(i+1, j+1)
// 

vector<int> ucs(vector<int> A, vector<int> B) {
  N = A.size(), M = B.size();
  if (A == B) return A;
  if (N > 3000 || M > 3000) return {-1};
  return lcs(A, B);
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 16
• Subtask 5: 0 / 14
• Subtask 6: 0 / 42