oj.uz

Submission #847745

# Submission time Handle Problem Language Result Execution time Memory
847745 2023-09-10T10:03:26 Z Adish Tracks in the Snow (BOI13_tracks) C++14
36.5625 / 100
 2000 ms 502204 KB 
#include <bits/stdc++.h>
using namespace std;
void bfs(char ch, vector<string>&s, set<pair<int,int>>&st, int n, int m){
    queue<pair<int, int>>q;
    q.push({0, 0});
    s[0][0] = ch ^ 'F' ^ 'R';
    st.erase({0, 0});
    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 and s[x][y] == ch){
                q.push({x, y});
                st.erase({x, y});
                s[x][y] = ch ^ 'F' ^ 'R';
            }
        }
    }
}
int main(){
    int h, w;
    cin >> h >> w;
    vector<string>s(h);
    for(int i = 0; i < h; i++){
        cin >> s[i];
    }
    int cnt = 0;
    set<pair<int, int>>st;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(s[i][j] != '.'){
                st.insert({i, j});
            }
        }
    }
    while(!st.empty()){
         cnt++;
         bfs(s[0][0], s, st, h, w);
    }
    cout << cnt << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 12180 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 83 ms 8024 KB Output is correct
5 Correct 122 ms 1584 KB Output is correct
6 Correct 2 ms 344 KB Output is correct
7 Correct 2 ms 344 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 152 ms 1856 KB Output is correct
11 Correct 18 ms 2392 KB Output is correct
12 Correct 159 ms 4360 KB Output is correct
13 Correct 119 ms 1720 KB Output is correct
14 Correct 116 ms 1368 KB Output is correct
15 Correct 1107 ms 9648 KB Output is correct
16 Correct 558 ms 12172 KB Output is correct
17 Correct 865 ms 6132 KB Output is correct
18 Correct 88 ms 8024 KB Output is correct

Subtask #2
6.5625 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2077 ms 1112 KB Time limit exceeded
2 Execution timed out 2005 ms 34940 KB Time limit exceeded
3 Execution timed out 2045 ms 225960 KB Time limit exceeded
4 Execution timed out 2020 ms 38368 KB Time limit exceeded
5 Execution timed out 2025 ms 231760 KB Time limit exceeded
6 Execution timed out 2052 ms 363736 KB Time limit exceeded
7 Execution timed out 2021 ms 1112 KB Time limit exceeded
8 Execution timed out 2021 ms 1112 KB Time limit exceeded
9 Correct 349 ms 1904 KB Output is correct
10 Correct 904 ms 932 KB Output is correct
11 Correct 817 ms 968 KB Output is correct
12 Execution timed out 2040 ms 856 KB Time limit exceeded
13 Execution timed out 2021 ms 34800 KB Time limit exceeded
14 Execution timed out 2039 ms 21100 KB Time limit exceeded
15 Execution timed out 2025 ms 16684 KB Time limit exceeded
16 Execution timed out 2056 ms 18256 KB Time limit exceeded
17 Execution timed out 2051 ms 89544 KB Time limit exceeded
18 Execution timed out 2037 ms 63824 KB Time limit exceeded
19 Execution timed out 2043 ms 38224 KB Time limit exceeded
20 Execution timed out 2021 ms 52212 KB Time limit exceeded
21 Execution timed out 2025 ms 128592 KB Time limit exceeded
22 Execution timed out 2031 ms 231680 KB Time limit exceeded
23 Execution timed out 2029 ms 170096 KB Time limit exceeded
24 Execution timed out 2040 ms 162032 KB Time limit exceeded
25 Execution timed out 2047 ms 260368 KB Time limit exceeded
26 Execution timed out 2064 ms 476132 KB Time limit exceeded
27 Execution timed out 2099 ms 502204 KB Time limit exceeded
28 Execution timed out 2039 ms 474380 KB Time limit exceeded
29 Execution timed out 2091 ms 480160 KB Time limit exceeded
30 Execution timed out 2095 ms 450632 KB Time limit exceeded
31 Execution timed out 2037 ms 421700 KB Time limit exceeded
32 Execution timed out 2050 ms 432324 KB Time limit exceeded