oj.uz

Submission #645314

# Submission time Handle Problem Language Result Execution time Memory
645314 2022-09-26T18:22:34 Z Hacv16 Zoo (COCI19_zoo) C++17
110 / 110
 50 ms 6288 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 1015;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

#define pb push_back
#define sz(x) (int) x.size()
#define fr first
#define sc second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define dbg(x) cerr << #x << ": " << "[ " << x << " ]\n"

int n, m, ans, d[MAX][MAX];
char t[MAX][MAX];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); 

    cin >> n >> m;

    memset(t, '*', sizeof(t));

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> t[i][j];
    
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            d[i][j] = INF;

    deque<pair<int, pii>> q;
    q.push_front({1, {1, 1}});

    d[1][1] = 1;

    while(q.size()){
        int x = q.front().sc.fr, y = q.front().sc.sc;
        q.pop_front();

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i], ny = y + dy[i];

            if(t[nx][ny] == '*') continue;

            int w = (t[x][y] == t[nx][ny] ? 0 : 1);

            if(d[nx][ny] > d[x][y] + w){
                d[nx][ny] = d[x][y] + w;

                if(w == 0) q.push_front({d[nx][ny], {nx, ny}});
                else q.push_back({d[nx][ny], {nx, ny}});
            }
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(d[i][j] == INF) continue;
            ans = max(ans, d[i][j]);
        }
    }

    cout << ans << '\n';

    return 0;
}

Subtask #1
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1480 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 1 ms 1620 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1748 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct

Subtask #2
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1480 KB Output is correct
5 Correct 1 ms 1748 KB Output is correct
6 Correct 1 ms 1748 KB Output is correct
7 Correct 1 ms 1748 KB Output is correct
8 Correct 1 ms 1620 KB Output is correct
9 Correct 1 ms 1620 KB Output is correct
10 Correct 1 ms 1748 KB Output is correct
11 Correct 1 ms 1620 KB Output is correct
12 Correct 1 ms 1748 KB Output is correct
13 Correct 1 ms 1620 KB Output is correct
14 Correct 1 ms 1748 KB Output is correct
15 Correct 1 ms 1620 KB Output is correct
16 Correct 17 ms 6196 KB Output is correct
17 Correct 17 ms 6192 KB Output is correct
18 Correct 18 ms 6288 KB Output is correct
19 Correct 19 ms 6228 KB Output is correct
20 Correct 19 ms 6192 KB Output is correct
21 Correct 45 ms 6056 KB Output is correct
22 Correct 50 ms 6040 KB Output is correct
23 Correct 45 ms 6060 KB Output is correct
24 Correct 48 ms 6248 KB Output is correct
25 Correct 48 ms 6228 KB Output is correct
26 Correct 47 ms 5980 KB Output is correct
27 Correct 46 ms 6108 KB Output is correct
28 Correct 46 ms 6068 KB Output is correct
29 Correct 48 ms 6228 KB Output is correct
30 Correct 47 ms 6244 KB Output is correct