oj.uz

Submission #971318

# Submission time Handle Problem Language Result Execution time Memory
971318 2024-04-28T11:12:45 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1362 ms 1048576 KB 
#include <bits/stdc++.h>
#define MAX_D 4001
#define MAX_D 4001

using namespace std;

int h, w;
char meadow[MAX_D][MAX_D];
int component[MAX_D][MAX_D];
vector<int> graph[MAX_D * MAX_D];
int d[MAX_D * MAX_D];

void floodfill(int x, int y, int cmp) {
    component[x][y] = cmp;
    if(x + 1 < h && meadow[x + 1][y] == meadow[x][y] && component[x + 1][y] == 0) {
        floodfill(x + 1, y, cmp);
    }
    if(x - 1 >= 0 && meadow[x - 1][y] == meadow[x][y] && component[x - 1][y] == 0) {
        floodfill(x - 1, y, cmp);
    }
    if(y + 1 < w && meadow[x][y + 1] == meadow[x][y] && component[x][y + 1] == 0) {
        floodfill(x, y + 1, cmp);
    }
    if(y - 1 >= 0 && meadow[x][y - 1] == meadow[x][y] && component[x][y - 1] == 0) {
        floodfill(x, y - 1, cmp);
    }
}

int main() {
    string tmps;
    cin >> h >> w;
    for(int i = 0; i < h; i++) {
        cin >> tmps;
        for(int j = 0; j < w; j++) {
            meadow[i][j] = tmps[j];
        }   
    }
    int cnt = 1;
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(component[i][j] == 0 && meadow[i][j] != '.') {
                floodfill(i, j, cnt);
                cnt++;
            }
        }
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(meadow[i][j] == '.') {
                continue;
            }
            if(i + 1 < h && meadow[i + 1][j] != '.' && component[i + 1][j] != component[i][j]) {
                graph[component[i + 1][j]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i + 1][j]);
            }
            if(i - 1 >= 0 && meadow[i - 1][j] != '.' && component[i - 1][j] != component[i][j]) {
                graph[component[i - 1][j]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i - 1][j]);
            }  
            if(j + 1 < w && meadow[i][j + 1] != '.' && component[i][j + 1] != component[i][j]) {
                graph[component[i][j + 1]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i][j + 1]);
            }  
            if(j - 1 >= 0 && meadow[i][j - 1] != '.' && component[i][j - 1] != component[i][j]) {
                graph[component[i][j - 1]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i][j - 1]);
            }     
        }
    }
    fill(d, d + cnt, -1);
    queue<pair<int, int>> q;
    d[component[0][0]] = 0;
    q.push({component[0][0], 0});
    while(!q.empty()) {
        pair<int, int> curr_node = q.front();
        q.pop();
        for(auto iter : graph[curr_node.first]) {
            if(d[iter] == -1) {
                d[iter] = curr_node.second + 1;
                q.push({iter, curr_node.second + 1});
            }
        }
    }
    int ans = 1;
    for(int i = 0; i < cnt; i++) {
        ans = max(ans, d[i] + 1);
    }
    cout << ans;
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 387668 KB Output is correct
2 Correct 121 ms 377424 KB Output is correct
3 Correct 125 ms 377540 KB Output is correct
4 Correct 140 ms 383844 KB Output is correct
5 Correct 124 ms 380244 KB Output is correct
6 Correct 123 ms 377208 KB Output is correct
7 Correct 127 ms 377564 KB Output is correct
8 Correct 176 ms 377848 KB Output is correct
9 Correct 132 ms 378120 KB Output is correct
10 Correct 136 ms 379984 KB Output is correct
11 Correct 173 ms 379704 KB Output is correct
12 Correct 128 ms 381712 KB Output is correct
13 Correct 139 ms 380216 KB Output is correct
14 Correct 135 ms 380220 KB Output is correct
15 Correct 145 ms 386268 KB Output is correct
16 Correct 153 ms 387576 KB Output is correct
17 Correct 172 ms 384300 KB Output is correct
18 Correct 131 ms 383916 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 408188 KB Output is correct
2 Correct 217 ms 404564 KB Output is correct
3 Correct 752 ms 512496 KB Output is correct
4 Correct 265 ms 417244 KB Output is correct
5 Correct 825 ms 580696 KB Output is correct
6 Correct 1069 ms 616000 KB Output is correct
7 Correct 134 ms 409720 KB Output is correct
8 Correct 133 ms 408220 KB Output is correct
9 Correct 125 ms 378704 KB Output is correct
10 Correct 119 ms 377940 KB Output is correct
11 Correct 136 ms 409056 KB Output is correct
12 Correct 131 ms 379060 KB Output is correct
13 Correct 226 ms 404640 KB Output is correct
14 Correct 180 ms 394880 KB Output is correct
15 Correct 177 ms 394580 KB Output is correct
16 Correct 168 ms 389848 KB Output is correct
17 Correct 383 ms 437492 KB Output is correct
18 Correct 339 ms 428624 KB Output is correct
19 Correct 267 ms 417284 KB Output is correct
20 Correct 274 ms 417632 KB Output is correct
21 Correct 497 ms 466776 KB Output is correct
22 Correct 848 ms 580408 KB Output is correct
23 Correct 638 ms 483476 KB Output is correct
24 Correct 518 ms 471392 KB Output is correct
25 Correct 1203 ms 536792 KB Output is correct
26 Runtime error 741 ms 1048576 KB Execution killed with signal 9
27 Correct 1061 ms 863164 KB Output is correct
28 Correct 1085 ms 615848 KB Output is correct
29 Correct 1010 ms 590584 KB Output is correct
30 Correct 1073 ms 661356 KB Output is correct
31 Correct 1362 ms 680976 KB Output is correct
32 Correct 1222 ms 902984 KB Output is correct