oj.uz

Submission #1105581

# Submission time Handle Problem Language Result Execution time Memory
1105581 2024-10-26T19:46:14 Z coolboy19521 Bajka (COCI20_bajka) C++17
0 / 70
 1000 ms 4324 KB 
#include "bits/stdc++.h"

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    if (m > n) {
        cout << "-1\n";
        return 0;
    }

    string s, t;
    cin >> s >> t;

    int alp = 26;

    vector<vector<int>> sm(alp);

    for (int i = 0; i < n; i++) {
        sm[s[i] - 'a'].push_back(i);
    }

    int maxr = 1e9;
    int mn = maxr;

    auto dijk = [&]() {
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> q;
        map<pair<int, int>, int> vi;

        for (int i : sm[t[0] - 'a']) {
            q.emplace(0, 0, i);
            vi[{0, i}] = 0;
        }

        while (!q.empty()) {
            auto [ds, at, ix] = q.top();
            q.pop();

            if (ds != vi[{at, ix}]) {
                continue;
            }

            if (at == m - 1) {
                mn = min(mn, ds);
            } else {
                for (int i : sm[t[at] - 'a']) {
                    int new_dist = ds + abs(i - ix);
                    if (!vi.count({at, i}) || new_dist < vi[{at, i}]) {
                        q.emplace(new_dist, at, i);
                        vi[{at, i}] = new_dist;
                    }
                }
                for (int i : {-1, 1}) {
                    if (0 <= ix + i && ix + i < n && at + 1 < m && t[at + 1] == s[ix + i]) {
                        int new_dist = ds + 1;
                        if (!vi.count({at + 1, ix + i}) || new_dist < vi[{at + 1, ix + i}]) {
                            q.emplace(new_dist, at + 1, ix + i);
                            vi[{at + 1, ix + i}] = new_dist;
                        }
                    }
                }
            }
        }
    };

    dijk();

    if (mn != maxr) {
        cout << mn << '\n';
    } else {
        cout << "-1\n";
    }
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 592 KB Output is correct
2 Correct 49 ms 800 KB Output is correct
3 Correct 14 ms 848 KB Output is correct
4 Correct 18 ms 848 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 182 ms 1816 KB Output is correct
8 Correct 609 ms 4324 KB Output is correct
9 Execution timed out 1062 ms 4096 KB Time limit exceeded
10 Halted 0 ms 0 KB -