oj.uz

Submission #1000526

# Submission time Handle Problem Language Result Execution time Memory
1000526 2024-06-17T16:29:48 Z HUYHDUVE Tracks in the Snow (BOI13_tracks) C++14
58.4375 / 100
 2000 ms 97876 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 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;
    vector<string> grid(n);
    for(auto &it : grid) cin >> it;

    vector<vector<int>> min_d(n, vector<int> (m, INF));
    min_d[0][0] = 1;
    deque<pii> q;
    q.push_back({0,0});
    int ans = 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] != INF || 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 1780 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 133 ms 1536 KB Output is correct
5 Correct 11 ms 856 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 12 ms 864 KB Output is correct
11 Correct 16 ms 600 KB Output is correct
12 Correct 44 ms 824 KB Output is correct
13 Correct 11 ms 860 KB Output is correct
14 Correct 11 ms 860 KB Output is correct
15 Correct 156 ms 1884 KB Output is correct
16 Correct 209 ms 1960 KB Output is correct
17 Correct 123 ms 1884 KB Output is correct
18 Correct 128 ms 1524 KB Output is correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 860 KB Output is correct
2 Correct 1455 ms 9808 KB Output is correct
3 Execution timed out 2056 ms 95312 KB Time limit exceeded
4 Execution timed out 2001 ms 22744 KB Time limit exceeded
5 Execution timed out 2009 ms 53588 KB Time limit exceeded
6 Execution timed out 2068 ms 96800 KB Time limit exceeded
7 Correct 90 ms 856 KB Output is correct
8 Correct 98 ms 860 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 53 ms 860 KB Output is correct
12 Correct 4 ms 348 KB Output is correct
13 Correct 1433 ms 9804 KB Output is correct
14 Correct 642 ms 5876 KB Output is correct
15 Correct 478 ms 6236 KB Output is correct
16 Correct 251 ms 4184 KB Output is correct
17 Execution timed out 2101 ms 24400 KB Time limit exceeded
18 Execution timed out 2043 ms 24148 KB Time limit exceeded
19 Correct 1947 ms 22864 KB Output is correct
20 Execution timed out 2056 ms 20820 KB Time limit exceeded
21 Execution timed out 2037 ms 56404 KB Time limit exceeded
22 Execution timed out 2048 ms 54100 KB Time limit exceeded
23 Execution timed out 2105 ms 46848 KB Time limit exceeded
24 Execution timed out 2101 ms 54672 KB Time limit exceeded
25 Execution timed out 2012 ms 96140 KB Time limit exceeded
26 Execution timed out 2009 ms 76216 KB Time limit exceeded
27 Execution timed out 2094 ms 97608 KB Time limit exceeded
28 Execution timed out 2070 ms 97692 KB Time limit exceeded
29 Execution timed out 2009 ms 97876 KB Time limit exceeded
30 Execution timed out 2082 ms 95840 KB Time limit exceeded
31 Execution timed out 2025 ms 62176 KB Time limit exceeded
32 Execution timed out 2066 ms 97588 KB Time limit exceeded