oj.uz

Submission #1000534

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

typedef pair<int,int> pii;
#define ff first
#define sc second

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.size()){
        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 218 ms 3920 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 144 ms 3676 KB Output is correct
5 Correct 17 ms 2140 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 856 KB Output is correct
10 Correct 13 ms 1840 KB Output is correct
11 Correct 16 ms 1692 KB Output is correct
12 Correct 46 ms 2092 KB Output is correct
13 Correct 12 ms 2140 KB Output is correct
14 Correct 12 ms 2136 KB Output is correct
15 Correct 191 ms 3724 KB Output is correct
16 Correct 231 ms 3920 KB Output is correct
17 Correct 122 ms 3588 KB Output is correct
18 Correct 145 ms 3664 KB Output is correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 15976 KB Output is correct
2 Correct 1421 ms 11864 KB Output is correct
3 Execution timed out 2065 ms 51792 KB Time limit exceeded
4 Execution timed out 2003 ms 29520 KB Time limit exceeded
5 Execution timed out 2066 ms 32636 KB Time limit exceeded
6 Execution timed out 2064 ms 47704 KB Time limit exceeded
7 Correct 100 ms 16712 KB Output is correct
8 Correct 102 ms 16012 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 68 ms 16424 KB Output is correct
12 Correct 5 ms 1116 KB Output is correct
13 Correct 1518 ms 11912 KB Output is correct
14 Correct 617 ms 8012 KB Output is correct
15 Correct 496 ms 10380 KB Output is correct
16 Correct 268 ms 4860 KB Output is correct
17 Execution timed out 2036 ms 19348 KB Time limit exceeded
18 Execution timed out 2017 ms 24520 KB Time limit exceeded
19 Correct 1991 ms 29444 KB Output is correct
20 Execution timed out 2102 ms 20460 KB Time limit exceeded
21 Execution timed out 2029 ms 34992 KB Time limit exceeded
22 Execution timed out 2027 ms 32684 KB Time limit exceeded
23 Execution timed out 2027 ms 28408 KB Time limit exceeded
24 Execution timed out 2080 ms 33588 KB Time limit exceeded
25 Execution timed out 2043 ms 53756 KB Time limit exceeded
26 Execution timed out 2094 ms 31536 KB Time limit exceeded
27 Execution timed out 2017 ms 37124 KB Time limit exceeded
28 Execution timed out 2005 ms 47628 KB Time limit exceeded
29 Execution timed out 2012 ms 41036 KB Time limit exceeded
30 Execution timed out 2087 ms 42052 KB Time limit exceeded
31 Execution timed out 2077 ms 36692 KB Time limit exceeded
32 Execution timed out 2090 ms 55348 KB Time limit exceeded