Submission #479064

#	Time	Username	Problem	Language	Result	Execution time	Memory
479064		lukameladze	Bajka (COCI20_bajka)	C++14	70 / 70	120 ms	3372 KiB

bajka

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
#define pii pair <int , int>
const int N = 305;
int idx1,anss[N][N],ans,cur,x,y,z,dist[N][N];
int n,m;
string s,s1;
vector < pair <int, int > > v[N];
vector <int> occ[N];
priority_queue < pair < int, pii > > q;
void go(int i, int cur) {
     if (cur > 1) {
          v[i].pb({cur - 1, abs(i-cur) + 1});//, cout<<i<<" "<<cur - 1<<" "<<abs(i-cur) +1<<endl;
     }
     if (cur < n) {
          v[i].pb({cur + 1,abs(i - cur) + 1});//, cout<<i<<" "<<cur + 1<<" "<<abs(i - cur) + 1<<endl;
     }
}
main() {
  std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
     cin>>n>>m;
     cin>>s>>s1;
     s ="@" + s;
     for (int i = 1; i <= n; i++) {
          occ[s[i]-'a'].pb(i);
     }
     for (int i = 1; i <= n; i++) {
          if (i > 1)
          v[i].pb({i - 1, 1});
          if (i < n) v[i].pb({i+1,1});
          for (int j = 0; j < occ[s[i]-'a'].size(); j++) {
               cur = occ[s[i]-'a'][j];
               if (cur == i) continue;
               go(i,cur);
          }
     }
     for (int i = 1; i <= n; i++) {
          for (int j= 1; j <= m; j++) {
               dist[i][j] = 1e9;
          }
     }
     s1 = "@" + s1;
     ans = 1e9;

     for (int i = 0; i < occ[s1[1]-'a'].size(); i++) {
          q.push({0,{occ[s1[1]-'a'][i],1}});
          dist[occ[s1[1]-'a'][i]][1] = 0;
     }
     while (!q.empty()) {
          x = -(q.top().f);
          y= q.top().s.f;
          z = q.top().s.s;
          //cout<<x<<" "<<y<<" "<<z<<endl;
          if (z == m) ans = min(ans,x);
          q.pop();
          if (dist[y][z] < x) continue;
          for (int j = 0; j < v[y].size(); j++) {
               int nxtid = v[y][j].f;
               if(s[nxtid] == s1[z + 1] && dist[nxtid][z+1] > dist[y][z] + v[y][j].s)  {
                    q.push({-(dist[y][z] + v[y][j].s), {nxtid,z+1}});
                    dist[nxtid][z+1] = dist[y][z] + v[y][j].s;
               }
          }
     } 
     if (ans >= 1e9) cout<<-1<<endl;
     else
     cout<<ans<<endl;
}

Compilation message (stderr)

bajka.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   22 | main() {
      | ^~~~
bajka.cpp: In function 'int main()':
bajka.cpp:34:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |           for (int j = 0; j < occ[s[i]-'a'].size(); j++) {
      |                           ~~^~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |      for (int i = 0; i < occ[s1[1]-'a'].size(); i++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~~~~~
bajka.cpp:60:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |           for (int j = 0; j < v[y].size(); j++) {
      |                           ~~^~~~~~~~~~~~~

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