Submission #860460

#TimeUsernameProblemLanguageResultExecution timeMemory
860460meliodasssfBajka (COCI20_bajka)C++17
70 / 70
7 ms4948 KiB
#include <bits/stdc++.h> //hi using namespace std; #define endl '\n' int n,m; string A,B; int L[100010],R[100010]; void in() { cin >> n >> m; cin >> A >> B; A = " " + A; B = " " + B; // for (int i=1; i<=n; i++) cout << A[i] << ' ' ; cout << endl; // for (int i=1; i<=n; i++) cout << B[i] << ' ' ; cout << endl; } map<char,int> mp; void set_up() { for(int i = 1; i <= n; i++) { if(mp.find(A[i]) != mp.end()) L[i] = mp[A[i]]; mp[A[i]] = i; } mp.clear(); for(int i = n; i >= 1; i--) { if(mp.find(A[i]) != mp.end()) R[i] = mp[A[i]]; mp[A[i]] = i; } mp.clear(); // for (int i=1; i<=n; i++) cout << L[i] << ' ' ; cout << endl; // for (int i=1; i<=n; i++) cout << R[i] << ' ' ; cout << endl; } long long dp[1010][1010]; bool visited[1010][1010]; struct path { pair<int,int> s; long long len; }; bool operator < (const path &a, const path &b) { return a.len > b.len; } void dijkstra() { priority_queue <path> pq; for (int i=1; i<=n; i++) { if(A[i] == B[1]) { pq.push(path{{1, i}, 0}); } } while(pq.empty() == false) { path p = pq.top(); pq.pop(); if(visited[p.s.first][p.s.second] == true) continue; visited[p.s.first][p.s.second] = true; dp[p.s.first][p.s.second] = p.len; if(p.s.first == m) continue; if(p.s.second > 1 && A[p.s.second - 1] == B[p.s.first + 1] && visited[p.s.first + 1][p.s.second - 1] == false) { pq.push(path{{p.s.first + 1, p.s.second - 1}, p.len + 1}); } if(p.s.second < n && A[p.s.second + 1] == B[p.s.first + 1] && visited[p.s.first + 1][p.s.second + 1] == false) { pq.push(path{{p.s.first + 1, p.s.second + 1}, p.len + 1}); } int pos1 = L[p.s.second]; int pos2 = R[p.s.second]; if(pos1 != 0 && visited[p.s.first][pos1] == false) { pq.push(path{{p.s.first, pos1}, p.len + abs(p.s.second - pos1)}); } if(pos2 != 0 && visited[p.s.first][pos2] == false) { pq.push(path{{p.s.first, pos2}, p.len + abs(p.s.second - pos2)}); } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); in(); set_up(); dijkstra(); long long res = LLONG_MAX; for (int i=1; i<=n; i++) { if(visited[m][i] == true) { res = min(res, dp[m][i]); } } if(res == LLONG_MAX) cout << -1; else cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...