oj.uz

Submission #971323

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

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];
queue<int> q;

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);
    d[component[0][0]] = 0;
    q.push(component[0][0]);
    while(!q.empty()) {
        int curr_node = q.front();
        q.pop();
        for(auto iter : graph[curr_node]) {
            if(d[iter] == -1) {
                d[iter] = d[curr_node] + 1;
                q.push(iter);
            }
        }
    }
    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 233 ms 387416 KB Output is correct
2 Correct 119 ms 377424 KB Output is correct
3 Correct 118 ms 377264 KB Output is correct
4 Correct 130 ms 383716 KB Output is correct
5 Correct 131 ms 380024 KB Output is correct
6 Correct 132 ms 377168 KB Output is correct
7 Correct 135 ms 377456 KB Output is correct
8 Correct 126 ms 377428 KB Output is correct
9 Correct 120 ms 377684 KB Output is correct
10 Correct 125 ms 379708 KB Output is correct
11 Correct 127 ms 379380 KB Output is correct
12 Correct 129 ms 381688 KB Output is correct
13 Correct 124 ms 379964 KB Output is correct
14 Correct 126 ms 379792 KB Output is correct
15 Correct 158 ms 386044 KB Output is correct
16 Correct 148 ms 387532 KB Output is correct
17 Correct 141 ms 383828 KB Output is correct
18 Correct 131 ms 383576 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 407888 KB Output is correct
2 Correct 222 ms 404540 KB Output is correct
3 Correct 835 ms 512176 KB Output is correct
4 Correct 279 ms 417108 KB Output is correct
5 Correct 778 ms 580388 KB Output is correct
6 Correct 1070 ms 614820 KB Output is correct
7 Correct 135 ms 409428 KB Output is correct
8 Correct 154 ms 407888 KB Output is correct
9 Correct 129 ms 378448 KB Output is correct
10 Correct 122 ms 377728 KB Output is correct
11 Correct 136 ms 408768 KB Output is correct
12 Correct 123 ms 378596 KB Output is correct
13 Correct 236 ms 404392 KB Output is correct
14 Correct 176 ms 394580 KB Output is correct
15 Correct 175 ms 394068 KB Output is correct
16 Correct 173 ms 389744 KB Output is correct
17 Correct 386 ms 437052 KB Output is correct
18 Correct 341 ms 428456 KB Output is correct
19 Correct 266 ms 416848 KB Output is correct
20 Correct 264 ms 417364 KB Output is correct
21 Correct 497 ms 466516 KB Output is correct
22 Correct 775 ms 580620 KB Output is correct
23 Correct 624 ms 483152 KB Output is correct
24 Correct 479 ms 470956 KB Output is correct
25 Correct 1174 ms 536532 KB Output is correct
26 Runtime error 707 ms 1048576 KB Execution killed with signal 9
27 Correct 1066 ms 862664 KB Output is correct
28 Correct 1047 ms 614680 KB Output is correct
29 Correct 981 ms 589860 KB Output is correct
30 Correct 1066 ms 660448 KB Output is correct
31 Correct 1317 ms 680648 KB Output is correct
32 Correct 1129 ms 902576 KB Output is correct