Submission #1221519

#TimeUsernameProblemLanguageResultExecution timeMemory
1221519nibertHieroglyphs (IOI24_hieroglyphs)C++20
0 / 100
1010 ms2162688 KiB
#include <iostream> #include <vector> using namespace std; vector<int> ucs(vector<int> A, vector<int> B) { int N = A.size(), M = B.size(); vector<vector<int>> dp(N + 1, vector<int>(M + 1, 0)); vector<vector<bool>> unique(N + 1, vector<bool>(M + 1, true)); // Fill dp table for (int i = N - 1; i >= 0; --i) { for (int j = M - 1; j >= 0; --j) { if (A[i] == B[j]) { dp[i][j] = 1 + dp[i + 1][j + 1]; unique[i][j] = unique[i + 1][j + 1]; } else { if (dp[i + 1][j] > dp[i][j + 1]) { dp[i][j] = dp[i + 1][j]; unique[i][j] = unique[i + 1][j]; } else if (dp[i + 1][j] < dp[i][j + 1]) { dp[i][j] = dp[i][j + 1]; unique[i][j] = unique[i][j + 1]; } else { dp[i][j] = dp[i + 1][j]; // same as dp[i][j+1] unique[i][j] = false; // two equal options → not unique } } } } if (!unique[0][0]) return {-1}; // multiple UCS paths // Reconstruct UCS vector<int> lcs; int i = 0, j = 0; while (i < N && j < M) { if (A[i] == B[j]) { lcs.push_back(A[i]); ++i; ++j; } else if (dp[i + 1][j] > dp[i][j + 1]) { ++i; } else { ++j; } } return lcs; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...