Submission #319573

#	Time	Username	Problem	Language	Result	Execution time	Memory
319573		BeanZ	Bajka (COCI20_bajka)	C++14	70 / 70	75 ms	6244 KiB

bajka

// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 305;
struct lpl{
    ll u, c, type;
};
vector<lpl> node[N];
ll d[N][N];
struct viet{
    ll u, t, c;
    bool operator <(const viet &o) const{
        return c > o.c;
    }
};
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("A.inp", "r")){
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    s = " " + s;
    t = " " + t;
    char st = t[1];
    char ed = t[m];
    for (int i = 1; i <= n; i++){
        for (int j = i + 1; j <= n; j++){
            if (s[i] == s[j]){
                node[i].push_back({j, j - i, 0});
                node[j].push_back({i, j - i, 0});
            }
        }
    }
    for (int i = 1; i < n; i++){
        node[i].push_back({i + 1, 1, 1});
    }
    for (int i = 2; i <= n; i++){
        node[i].push_back({i - 1, 1, 1});
    }
    priority_queue<viet> pq;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) d[i][j] = 1e18;
    for (int i = 1; i <= n; i++){
        if (s[i] == st){
            d[i][1] = 0;
            pq.push({i, 1, 0});
        }
    }
    while (pq.size()){
        viet x = pq.top();
        pq.pop();
        if (x.c != d[x.u][x.t]) continue;
        //cout << x.u << " " << x.t << endl;
        for (auto j : node[x.u]){
            if (j.type == 1){
                if (s[j.u] == t[x.t + 1]){
                    if (d[j.u][x.t + 1] > (x.c + j.c)){
                        d[j.u][x.t + 1] = x.c + j.c;
                        pq.push({j.u, x.t + 1, x.c + j.c});
                    }
                }
            } else {
                if (d[j.u][x.t] > (x.c + j.c)){
                    d[j.u][x.t] = x.c + j.c;
                    pq.push({j.u, x.t, x.c + j.c});
                }
            }
        }
    }
    ll ans = 1e18;
    for (int i = 1; i <= n; i++){
        if (ed == s[i]) ans = min(ans, d[i][m]);
    }
    if (ans < 1e18) cout << ans;
    else cout << -1;
}
/*
*/

Compilation message (stderr)

bajka.cpp: In function 'int main()':
bajka.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   22 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50