oj.uz

Submission #747290

# Submission time Handle Problem Language Result Execution time Memory
747290 2023-05-24T03:58:01 Z Trunkty Zoo (COCI19_zoo) C++14
110 / 110
 67 ms 43556 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[1000005];
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 13 ms 23764 KB Output is correct
2 Correct 13 ms 23836 KB Output is correct
3 Correct 14 ms 23852 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 13 ms 24460 KB Output is correct
6 Correct 13 ms 24488 KB Output is correct
7 Correct 13 ms 24392 KB Output is correct
8 Correct 13 ms 24468 KB Output is correct
9 Correct 12 ms 24404 KB Output is correct
10 Correct 13 ms 24404 KB Output is correct
11 Correct 15 ms 24412 KB Output is correct
12 Correct 13 ms 24524 KB Output is correct
13 Correct 13 ms 24308 KB Output is correct
14 Correct 13 ms 24384 KB Output is correct
15 Correct 12 ms 24308 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 13 ms 23836 KB Output is correct
3 Correct 14 ms 23852 KB Output is correct
4 Correct 12 ms 24020 KB Output is correct
5 Correct 13 ms 24460 KB Output is correct
6 Correct 13 ms 24488 KB Output is correct
7 Correct 13 ms 24392 KB Output is correct
8 Correct 13 ms 24468 KB Output is correct
9 Correct 12 ms 24404 KB Output is correct
10 Correct 13 ms 24404 KB Output is correct
11 Correct 15 ms 24412 KB Output is correct
12 Correct 13 ms 24524 KB Output is correct
13 Correct 13 ms 24308 KB Output is correct
14 Correct 13 ms 24384 KB Output is correct
15 Correct 12 ms 24308 KB Output is correct
16 Correct 31 ms 31640 KB Output is correct
17 Correct 31 ms 31760 KB Output is correct
18 Correct 36 ms 31500 KB Output is correct
19 Correct 33 ms 32988 KB Output is correct
20 Correct 32 ms 32204 KB Output is correct
21 Correct 66 ms 42732 KB Output is correct
22 Correct 61 ms 42644 KB Output is correct
23 Correct 62 ms 42896 KB Output is correct
24 Correct 66 ms 43556 KB Output is correct
25 Correct 66 ms 43284 KB Output is correct
26 Correct 67 ms 42876 KB Output is correct
27 Correct 66 ms 42700 KB Output is correct
28 Correct 62 ms 42540 KB Output is correct
29 Correct 65 ms 43484 KB Output is correct
30 Correct 63 ms 43092 KB Output is correct