oj.uz

Submission #747289

# Submission time Handle Problem Language Result Execution time Memory
747289 2023-05-24T03:57:40 Z Trunkty Zoo (COCI19_zoo) C++14
45 / 110
 36 ms 21076 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int r,c,ans;
char arr[1005][1005];
vector<pair<int,int>> bfs[100005];
int best[1005][1005];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin >> arr[i][j];
        }
    }
    best[1][1] = 1;
    bfs[1].push_back({1,1});
    for(int i=1;i<=r*c;i++){
        if(bfs[i].size()>0){
            ans = i;
        }
        for(int j=0;j<bfs[i].size();j++){
            int x = bfs[i][j].first, y = bfs[i][j].second;
            if(x!=1 and arr[x-1][y]!='*' and !best[x-1][y]){
                if(arr[x-1][y]!=arr[x][y]){
                    best[x-1][y] = best[x][y]+1;
                    bfs[best[x-1][y]].push_back({x-1,y});
                }
                else{
                    best[x-1][y] = best[x][y];
                    bfs[best[x-1][y]].push_back({x-1,y});
                }
            }
            if(x!=r and arr[x+1][y]!='*' and !best[x+1][y]){
                if(arr[x+1][y]!=arr[x][y]){
                    best[x+1][y] = best[x][y]+1;
                    bfs[best[x+1][y]].push_back({x+1,y});
                }
                else{
                    best[x+1][y] = best[x][y];
                    bfs[best[x+1][y]].push_back({x+1,y});
                }
            }
            if(y!=1 and arr[x][y-1]!='*' and !best[x][y-1]){
                if(arr[x][y-1]!=arr[x][y]){
                    best[x][y-1] = best[x][y]+1;
                    bfs[best[x][y-1]].push_back({x,y-1});
                }
                else{
                    best[x][y-1] = best[x][y];
                    bfs[best[x][y-1]].push_back({x,y-1});
                }
            }
            if(y!=c and arr[x][y+1]!='*' and !best[x][y+1]){
                if(arr[x][y+1]!=arr[x][y]){
                    best[x][y+1] = best[x][y]+1;
                    bfs[best[x][y+1]].push_back({x,y+1});
                }
                else{
                    best[x][y+1] = best[x][y];
                    bfs[best[x][y+1]].push_back({x,y+1});
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

Compilation message

zoo.cpp: In function 'int main()':
zoo.cpp:26:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int j=0;j<bfs[i].size();j++){
      |                     ~^~~~~~~~~~~~~~

Subtask #1
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 1 ms 2900 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 1 ms 2772 KB Output is correct
4 Correct 1 ms 2900 KB Output is correct
5 Correct 2 ms 3284 KB Output is correct
6 Correct 2 ms 3284 KB Output is correct
7 Correct 2 ms 3284 KB Output is correct
8 Correct 2 ms 3284 KB Output is correct
9 Correct 2 ms 3284 KB Output is correct
10 Correct 2 ms 3284 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3284 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 2 ms 3156 KB Output is correct
16 Runtime error 36 ms 21076 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -