oj.uz

Submission #348384

# Submission time Handle Problem Language Result Execution time Memory
348384 2021-01-14T20:44:11 Z oleksg Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 1558 ms 128764 KB 
#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include<bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;

int n, m;

char arr[4001][4001];
int dist[4001][4001];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};
bool inside(int x, int y){
    if (x < 0 || x >= n){
        return false;
    }
    if (y < 0 || y >= m){
        return false;
    }
    if (arr[x][y] == '.'){
        return false;
    }
    return true;
}
int main(){
    cin >> n >> m;
    for (int x = 0; x < n; x++){
        for (int y = 0; y < m; y++){
            cin >> arr[x][y];
            dist[x][y] = -1;
        }
    }
    int answer = 1;
    deque<pair<int, int>> q;
    dist[0][0] = 1;
    q.push_back({0, 0});
    while(q.size() > 0){
        pair<int, int> cur = q.front();
        q.pop_front();
        answer = max(answer, dist[cur.first][cur.second]);
        for (int z = 0; z < 4; z++){
            int nx = cur.first + dx[z];
            int ny = cur.second + dy[z];
            if (inside(nx, ny) && dist[nx][ny] == -1){
                if (arr[nx][ny] == arr[cur.first][cur.second]){
                    dist[nx][ny] = dist[cur.first][cur.second];
                    q.push_front({nx, ny});
                }
                else{
                    dist[nx][ny] = dist[cur.first][cur.second] + 1;
                    q.push_back({nx, ny});
                }
            }
        }
    }
    cout << answer << "\n";

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 5484 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 17 ms 5100 KB Output is correct
5 Correct 8 ms 3052 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 7 ms 2668 KB Output is correct
11 Correct 5 ms 2156 KB Output is correct
12 Correct 10 ms 3052 KB Output is correct
13 Correct 8 ms 3052 KB Output is correct
14 Correct 8 ms 3052 KB Output is correct
15 Correct 26 ms 5484 KB Output is correct
16 Correct 27 ms 5484 KB Output is correct
17 Correct 23 ms 5228 KB Output is correct
18 Correct 17 ms 5100 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 30956 KB Output is correct
2 Correct 134 ms 17920 KB Output is correct
3 Correct 1137 ms 88428 KB Output is correct
4 Correct 289 ms 33644 KB Output is correct
5 Correct 694 ms 67820 KB Output is correct
6 Correct 1558 ms 102128 KB Output is correct
7 Correct 21 ms 32236 KB Output is correct
8 Correct 21 ms 30956 KB Output is correct
9 Correct 5 ms 748 KB Output is correct
10 Correct 3 ms 492 KB Output is correct
11 Correct 20 ms 31724 KB Output is correct
12 Correct 3 ms 1644 KB Output is correct
13 Correct 135 ms 17900 KB Output is correct
14 Correct 82 ms 12012 KB Output is correct
15 Correct 83 ms 13292 KB Output is correct
16 Correct 57 ms 6764 KB Output is correct
17 Correct 350 ms 36184 KB Output is correct
18 Correct 323 ms 35840 KB Output is correct
19 Correct 288 ms 33724 KB Output is correct
20 Correct 254 ms 31232 KB Output is correct
21 Correct 676 ms 70252 KB Output is correct
22 Correct 688 ms 67948 KB Output is correct
23 Correct 656 ms 56940 KB Output is correct
24 Correct 664 ms 69480 KB Output is correct
25 Correct 1375 ms 88172 KB Output is correct
26 Correct 1081 ms 128764 KB Output is correct
27 Correct 1424 ms 117888 KB Output is correct
28 Correct 1554 ms 101996 KB Output is correct
29 Correct 1548 ms 100256 KB Output is correct
30 Correct 1485 ms 106976 KB Output is correct
31 Correct 1207 ms 73452 KB Output is correct
32 Correct 1363 ms 110240 KB Output is correct