oj.uz

Submission #1000528

# Submission time Handle Problem Language Result Execution time Memory
1000528 2024-06-17T16:33:32 Z HUYHDUVE Tracks in the Snow (BOI13_tracks) C++14
60.625 / 100
 2000 ms 44692 KB 
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
#define ff first
#define sc second
int const INF = 2e9;

vector<int> di = {1, -1, 0, 0}, dj = {0, 0, 1, -1};

int n, m, min_d[4000][4000], ans = 1;
string grid[4000];

int main(){
//    freopen("A.IN", "r", stdin);
//    freopen("A.OUT", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);


    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> grid[i];

    min_d[0][0] = 1;
    deque<pii> q;
    q.push_back({0,0});

    while(!q.empty()){
        pii cur = q.front();
        q.pop_front();
        ans = max(ans, min_d[cur.ff][cur.sc]);

        for(int i = 0; i < n; i++){
            int ni = cur.ff + di[i];
            int nj = cur.sc + dj[i];
            if(ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if(min_d[ni][nj] != 0 || grid[ni][nj] == '.') continue;

            if(grid[cur.ff][cur.sc] == grid[ni][nj]){
                min_d[ni][nj] = min_d[cur.ff][cur.sc];
                q.push_front({ni, nj});
            }
            else {
                min_d[ni][nj] = min_d[cur.ff][cur.sc] + 1;
                q.push_back({ni, nj});
            }
        }
    }

    cout << ans;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 3924 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 133 ms 3588 KB Output is correct
5 Correct 11 ms 2140 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 13 ms 1832 KB Output is correct
11 Correct 15 ms 1628 KB Output is correct
12 Correct 45 ms 2128 KB Output is correct
13 Correct 11 ms 2140 KB Output is correct
14 Correct 11 ms 1956 KB Output is correct
15 Correct 168 ms 3716 KB Output is correct
16 Correct 251 ms 3924 KB Output is correct
17 Correct 94 ms 3668 KB Output is correct
18 Correct 136 ms 3664 KB Output is correct

Subtask #2
30.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 16012 KB Output is correct
2 Correct 1408 ms 11344 KB Output is correct
3 Execution timed out 2033 ms 44692 KB Time limit exceeded
4 Correct 1866 ms 27868 KB Output is correct
5 Execution timed out 2037 ms 29012 KB Time limit exceeded
6 Execution timed out 2091 ms 42272 KB Time limit exceeded
7 Correct 104 ms 16732 KB Output is correct
8 Correct 106 ms 15824 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 63 ms 16212 KB Output is correct
12 Correct 6 ms 1116 KB Output is correct
13 Correct 1505 ms 11364 KB Output is correct
14 Correct 630 ms 7764 KB Output is correct
15 Correct 502 ms 10128 KB Output is correct
16 Correct 272 ms 4948 KB Output is correct
17 Execution timed out 2025 ms 17744 KB Time limit exceeded
18 Execution timed out 2036 ms 20852 KB Time limit exceeded
19 Correct 1989 ms 25684 KB Output is correct
20 Execution timed out 2059 ms 17220 KB Time limit exceeded
21 Execution timed out 2067 ms 26200 KB Time limit exceeded
22 Execution timed out 2068 ms 24148 KB Time limit exceeded
23 Execution timed out 2052 ms 20812 KB Time limit exceeded
24 Execution timed out 2031 ms 24716 KB Time limit exceeded
25 Execution timed out 2077 ms 38228 KB Time limit exceeded
26 Execution timed out 2057 ms 19796 KB Time limit exceeded
27 Execution timed out 2028 ms 21840 KB Time limit exceeded
28 Execution timed out 2061 ms 34132 KB Time limit exceeded
29 Execution timed out 2044 ms 26612 KB Time limit exceeded
30 Execution timed out 2052 ms 28456 KB Time limit exceeded
31 Execution timed out 2050 ms 26704 KB Time limit exceeded
32 Execution timed out 2057 ms 40792 KB Time limit exceeded