oj.uz

답안 #741723

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
741723 2023-05-14T16:54:59 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-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;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1082 ms 596 KB Time limit exceeded
2 Halted 0 ms 0 KB -