oj.uz

Submission #741720

# Submission time Handle Problem Language Result Execution time Memory
741720 2023-05-14T16:42:06 Z hfoliacots Bajka (COCI20_bajka) C++14
0 / 70
 1000 ms 596 KB 
#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) 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]]) { //auto i: l[t[0]][0]
			if (s[i.first] == t[1]) {
				ans = min(ans, par(i.first, 1, 1));
			} 
		}
	}
	if (ans < 1e9) cout << ans-1 << endl;
	else cout << -1 << endl;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -