oj.uz

Submission #319573

# Submission time Handle Problem Language Result Execution time Memory
319573 2020-11-05T14:13:54 Z BeanZ Bajka (COCI20_bajka) C++14
70 / 70
 75 ms 6244 KB 
// 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

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.0 / 20.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1792 KB Output is correct
2 Correct 5 ms 2284 KB Output is correct
3 Correct 3 ms 1516 KB Output is correct
4 Correct 3 ms 1516 KB Output is correct
5 Correct 1 ms 1292 KB Output is correct
6 Correct 1 ms 1260 KB Output is correct
7 Correct 23 ms 2608 KB Output is correct
8 Correct 75 ms 6244 KB Output is correct
9 Correct 51 ms 5376 KB Output is correct
10 Correct 1 ms 1260 KB Output is correct
11 Correct 14 ms 2156 KB Output is correct