oj.uz

Submission #1000523

# Submission time Handle Problem Language Result Execution time Memory
1000523 2024-06-17T16:27:41 Z HUYHDUVE Tracks in the Snow (BOI13_tracks) C++14
58.4375 / 100
 2000 ms 110236 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);
    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 238 ms 2392 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 153 ms 1812 KB Output is correct
5 Correct 18 ms 860 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 15 ms 892 KB Output is correct
11 Correct 17 ms 760 KB Output is correct
12 Correct 51 ms 860 KB Output is correct
13 Correct 13 ms 860 KB Output is correct
14 Correct 14 ms 856 KB Output is correct
15 Correct 186 ms 2164 KB Output is correct
16 Correct 242 ms 2388 KB Output is correct
17 Correct 109 ms 1884 KB Output is correct
18 Correct 148 ms 1572 KB Output is correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 856 KB Output is correct
2 Correct 1550 ms 10580 KB Output is correct
3 Execution timed out 2025 ms 108880 KB Time limit exceeded
4 Correct 1977 ms 26004 KB Output is correct
5 Execution timed out 2067 ms 55892 KB Time limit exceeded
6 Execution timed out 2033 ms 110164 KB Time limit exceeded
7 Correct 104 ms 924 KB Output is correct
8 Correct 108 ms 908 KB Output is correct
9 Correct 3 ms 856 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 63 ms 920 KB Output is correct
12 Correct 4 ms 488 KB Output is correct
13 Correct 1572 ms 10524 KB Output is correct
14 Correct 639 ms 6492 KB Output is correct
15 Correct 577 ms 7504 KB Output is correct
16 Correct 282 ms 4348 KB Output is correct
17 Execution timed out 2056 ms 27988 KB Time limit exceeded
18 Execution timed out 2045 ms 27472 KB Time limit exceeded
19 Execution timed out 2067 ms 25976 KB Time limit exceeded
20 Execution timed out 2084 ms 23888 KB Time limit exceeded
21 Execution timed out 2023 ms 57760 KB Time limit exceeded
22 Execution timed out 2093 ms 55888 KB Time limit exceeded
23 Execution timed out 2064 ms 47700 KB Time limit exceeded
24 Execution timed out 2064 ms 56764 KB Time limit exceeded
25 Execution timed out 2027 ms 108884 KB Time limit exceeded
26 Execution timed out 2048 ms 75760 KB Time limit exceeded
27 Execution timed out 2070 ms 110236 KB Time limit exceeded
28 Execution timed out 2071 ms 110180 KB Time limit exceeded
29 Execution timed out 2050 ms 110172 KB Time limit exceeded
30 Execution timed out 2075 ms 107884 KB Time limit exceeded
31 Execution timed out 2049 ms 63336 KB Time limit exceeded
32 Execution timed out 2037 ms 109904 KB Time limit exceeded