oj.uz

Submission #479063

# Submission time Handle Problem Language Result Execution time Memory
479063 2021-10-09T20:01:13 Z lukameladze Bajka (COCI20_bajka) C++14
20 / 70
 1000 ms 1396 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N = 305;
int idx1,anss[N][N],ans,cur;
int n,m;
string s,s1;
vector < pair <int, int > > v[N];
vector <int> occ[N];
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;
     }
}
void dfs(int idx, int idx1, int dist) {
     
     if (anss[idx][idx1] <= dist) return ;
     if (s[idx] != s1[idx1]) return ;
      anss[idx][idx1] = dist;
     if (idx1 == m) {
          ans = min(ans,dist);
          return ;
     }
     for (int j = 0; j < v[idx].size(); j++) {
          dfs(v[idx][j].f, idx1 + 1, dist + v[idx][j].s);
     }
}
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++) {
          for (int j = 1;j  <= m; j++) {
               anss[i][j] =1e9;
          }
     }
     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);
          }
     }
     s1 = "@" + s1;
     ans = 1e9;
     for (int i = 0; i < occ[s1[1]-'a'].size(); i++) {
          dfs(occ[s1[1]-'a'][i],1, 0);
     }
     if (ans >= 1e9) cout<<-1<<endl;
     else
     cout<<ans<<endl;
}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 972 KB Output is correct
2 Correct 727 ms 1396 KB Output is correct
3 Correct 223 ms 864 KB Output is correct
4 Correct 416 ms 972 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Execution timed out 1088 ms 1228 KB Time limit exceeded
8 Halted 0 ms 0 KB -