oj.uz

Submission #741699

# Submission time Handle Problem Language Result Execution time Memory
741699 2023-05-14T15:11:09 Z Alma Bajka (COCI20_bajka) C++17
20 / 70
 1000 ms 1620 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m;
	string s, t;
	cin >> n >> m >> s >> t;
	vector<set<pair<int, int>>> graph(n);
	
	for (int i = 0; i < n; i++) {
		if (i > 0) {
			graph[i].insert({i-1, 1});
			graph[i-1].insert({i, 1});
		} else if (i < n-1) {
			graph[i].insert({i+1, 1});
			graph[i+1].insert({i, 1});
		}
		for (int j = 0; j < n; j++) {
			if (s[i] == s[j]) { // add s[j] adjacents
				if (j > 0 && i != j-1) {
					graph[i].insert({j-1, abs(i - (j-1))});
					graph[j-1].insert({i, abs(i - (j-1))});
				} else if (j < n-1 && i != j+1) {
					graph[i].insert({j+1, abs(i - (j+1))});
					graph[j+1].insert({i, abs(i - (j+1))});
				}
			}
		}
	}

	priority_queue<pair<int, pair<int, int>>> pq; // cost, s_i, t_j
	vector<vector<int>> dp(n, vector<int>(m, 1e9));
	
	for (int i = 0; i < n; i++) {
		if (s[i] == t[0]) {
			pq.push({0, {i, 0}});
			dp[i][0] = 0;
		}
	}

	while (!pq.empty()) {
		int cost = pq.top().first;
		int i = pq.top().second.first;
		int j = pq.top().second.second;
		pq.pop();

		dp[i][j] = min(dp[i][j], cost);

		if (j == m-1) {
			continue;
		}

		for (pair<int, int> p: graph[i]) {
			int k = p.first;
			int c = p.second;
			if (s[k] == t[j+1] && cost + c <= dp[k][j+1]) {
				pq.push({cost + c, {k, j+1}});
			}
		}
	}

	int ans = 1e9;
	for (int i = 0; i < n; i++) {
		ans = min(ans, dp[i][m-1]);
	}
	if (ans == 1e9) ans = -1;
	
	cout << ans << '\n';

	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 50.0

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