oj.uz

Submission #847753

# Submission time Handle Problem Language Result Execution time Memory
847753 2023-09-10T10:28:48 Z Adish Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1420 ms 249132 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 40001;
int ans = 0;
vector<vector<bool>> vis(N, vector<bool>(N, false));
void bfs(vector<string>&s, int n, int m){
    queue<pair<int, int>>altr_q, q;
    altr_q.push({0, 0});
    vis[0][0] = true;
    while(!altr_q.empty()){
        ans++;
        q = altr_q;
        queue<pair<int, int>>q_;
        altr_q = q_;
        while(!q.empty()){
            pair<int, int>tp = q.front();
            q.pop();
            vector<int> dx = {-1, 0, 1, 0};
            vector<int> dy = {0, 1, 0, -1};
            for(int i = 0; i < 4; i++){
                int x = tp.first + dx[i];
                int y = tp.second + dy[i];
                if(x >= 0 and x < n and y >=0 and y < m){
                    if(s[x][y] == '.' or vis[x][y]){
                        continue;
                    }
                    vis[x][y] = true;
                    if(s[x][y] == s[tp.first][tp.second]){
                        q.push({x, y});
                    }
                    else{
                        altr_q.push({x, y});
                    }
                }
            }
        }
    }
}
int main(){
    int h, w;
    cin >> h >> w;
    vector<string>s(h);
    for(int i = 0; i < h; i++){
        cin >> s[i];
    }
    bfs(s, h, w);
    cout << ans << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 199436 KB Output is correct
2 Correct 94 ms 198584 KB Output is correct
3 Correct 90 ms 198476 KB Output is correct
4 Correct 113 ms 199248 KB Output is correct
5 Correct 91 ms 198736 KB Output is correct
6 Correct 92 ms 198484 KB Output is correct
7 Correct 94 ms 198604 KB Output is correct
8 Correct 92 ms 198468 KB Output is correct
9 Correct 93 ms 198480 KB Output is correct
10 Correct 99 ms 198992 KB Output is correct
11 Correct 93 ms 198616 KB Output is correct
12 Correct 98 ms 198736 KB Output is correct
13 Correct 95 ms 198736 KB Output is correct
14 Correct 99 ms 198800 KB Output is correct
15 Correct 114 ms 199760 KB Output is correct
16 Correct 111 ms 199248 KB Output is correct
17 Correct 103 ms 199248 KB Output is correct
18 Correct 101 ms 199248 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 198736 KB Output is correct
2 Correct 159 ms 201860 KB Output is correct
3 Correct 556 ms 236896 KB Output is correct
4 Correct 198 ms 205692 KB Output is correct
5 Correct 640 ms 214472 KB Output is correct
6 Correct 1409 ms 249132 KB Output is correct
7 Correct 92 ms 198736 KB Output is correct
8 Correct 98 ms 198716 KB Output is correct
9 Correct 95 ms 198736 KB Output is correct
10 Correct 94 ms 198448 KB Output is correct
11 Correct 94 ms 198736 KB Output is correct
12 Correct 94 ms 198632 KB Output is correct
13 Correct 166 ms 201040 KB Output is correct
14 Correct 130 ms 200164 KB Output is correct
15 Correct 128 ms 200528 KB Output is correct
16 Correct 125 ms 199196 KB Output is correct
17 Correct 279 ms 206160 KB Output is correct
18 Correct 277 ms 206232 KB Output is correct
19 Correct 199 ms 205640 KB Output is correct
20 Correct 196 ms 205168 KB Output is correct
21 Correct 371 ms 210256 KB Output is correct
22 Correct 640 ms 214608 KB Output is correct
23 Correct 471 ms 208208 KB Output is correct
24 Correct 431 ms 214864 KB Output is correct
25 Correct 785 ms 237072 KB Output is correct
26 Correct 1040 ms 211968 KB Output is correct
27 Correct 1287 ms 232364 KB Output is correct
28 Correct 1420 ms 249056 KB Output is correct
29 Correct 1339 ms 245828 KB Output is correct
30 Correct 1234 ms 243424 KB Output is correct
31 Correct 1088 ms 211640 KB Output is correct
32 Correct 1164 ms 230324 KB Output is correct