oj.uz

Submission #847751

# Submission time Handle Problem Language Result Execution time Memory
847751 2023-09-10T10:21:36 Z Adish Tracks in the Snow (BOI13_tracks) C++14
91.25 / 100
 1416 ms 1048576 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>>&q){
    ans++;
    queue<pair<int, int>>altr_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});
                }
            }
        }
    }
    if(!altr_q.empty()){
        bfs(s, n, m, altr_q);
    }
}
int main(){
    int h, w;
    cin >> h >> w;
    vector<string>s(h);
    for(int i = 0; i < h; i++){
        cin >> s[i];
    }
    queue<pair<int, int>>q;
    q.push({0, 0});
    vis[0][0] = true;
    bfs(s, h, w, q);
    cout << ans << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 198992 KB Output is correct
2 Correct 91 ms 198740 KB Output is correct
3 Correct 91 ms 198480 KB Output is correct
4 Correct 100 ms 198992 KB Output is correct
5 Correct 94 ms 198736 KB Output is correct
6 Correct 89 ms 198740 KB Output is correct
7 Correct 91 ms 198480 KB Output is correct
8 Correct 94 ms 198484 KB Output is correct
9 Correct 90 ms 198480 KB Output is correct
10 Correct 91 ms 198736 KB Output is correct
11 Correct 94 ms 198640 KB Output is correct
12 Correct 103 ms 198580 KB Output is correct
13 Correct 97 ms 198736 KB Output is correct
14 Correct 93 ms 198820 KB Output is correct
15 Correct 107 ms 199036 KB Output is correct
16 Correct 107 ms 199004 KB Output is correct
17 Correct 99 ms 199036 KB Output is correct
18 Correct 100 ms 198980 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 203088 KB Output is correct
2 Correct 157 ms 201700 KB Output is correct
3 Correct 959 ms 736800 KB Output is correct
4 Correct 204 ms 208460 KB Output is correct
5 Runtime error 651 ms 1048576 KB Execution killed with signal 9
6 Correct 1409 ms 247500 KB Output is correct
7 Correct 104 ms 202576 KB Output is correct
8 Correct 107 ms 202992 KB Output is correct
9 Correct 103 ms 199008 KB Output is correct
10 Correct 101 ms 200784 KB Output is correct
11 Correct 104 ms 200528 KB Output is correct
12 Correct 104 ms 207956 KB Output is correct
13 Correct 167 ms 202772 KB Output is correct
14 Correct 146 ms 201828 KB Output is correct
15 Correct 219 ms 323892 KB Output is correct
16 Correct 133 ms 200444 KB Output is correct
17 Correct 299 ms 211916 KB Output is correct
18 Correct 565 ms 682724 KB Output is correct
19 Correct 202 ms 208464 KB Output is correct
20 Correct 266 ms 310864 KB Output is correct
21 Correct 563 ms 499968 KB Output is correct
22 Runtime error 630 ms 1048576 KB Execution killed with signal 9
23 Correct 486 ms 217680 KB Output is correct
24 Runtime error 673 ms 1048576 KB Execution killed with signal 9
25 Runtime error 840 ms 1048576 KB Execution killed with signal 9
26 Correct 1100 ms 218148 KB Output is correct
27 Correct 1342 ms 239088 KB Output is correct
28 Correct 1416 ms 247620 KB Output is correct
29 Correct 1367 ms 245924 KB Output is correct
30 Correct 1258 ms 243832 KB Output is correct
31 Correct 1120 ms 217872 KB Output is correct
32 Correct 1183 ms 237860 KB Output is correct