This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vp = vector<pii>;
using vvp = vector<vp>;
int n, m;
string s, t;
vvp g;
int par(int a, int pos, int tim) {
if (pos == m-1) return tim;
if (t[pos] != s[a]) return 1e9;
int mi = 1e9;
for (int i = 0; i < (int)g[a].size(); i++) {
mi = min(mi, par(g[a][i].first, pos+1, tim + g[a][i].second));
}
return mi;
}
int main() {
cin >> n >> m;
cin >> s >> t;
g = vvp(n, vp());
map<char, vector<int>> l;
for (int i = 0; i < n; i++) {
if (i < n-1) g[i].push_back({i+1, 1});
if (i > 0) g[i].push_back({i-1, 1});
if (l.find(s[i]) != l.end()) {
for (int j: l[s[i]]) {
if (j > 0) g[i].push_back({j-1, abs(i-j)+1});
if (j < n-1) g[i].push_back({j+1, abs(i-j)+1});
if (i < n-1) g[j].push_back({i+1, abs(i-j)+1});
if (i > 0) g[j].push_back({i-1, abs(i-j)+1});
}
}
l[s[i]].push_back(i);
}
int ans = 1e9;
if (l.find(t[0]) != l.end()) {
for (auto i: g[l[t[0]][0]]) { // el vector de una de les primeres lletres
if (s[i.first] == t[1]) {
ans = min(ans, par(i.first, 1, 1));
}
}
}
if (ans < 1e9) cout << ans << endl;
else cout << -1 << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |