oj.uz

Submission #971320

# Submission time Handle Problem Language Result Execution time Memory
971320 2024-04-28T11:14:06 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1388 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];

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 226 ms 387680 KB Output is correct
2 Correct 120 ms 377212 KB Output is correct
3 Correct 118 ms 377428 KB Output is correct
4 Correct 129 ms 383824 KB Output is correct
5 Correct 128 ms 379988 KB Output is correct
6 Correct 119 ms 377168 KB Output is correct
7 Correct 134 ms 377452 KB Output is correct
8 Correct 119 ms 377484 KB Output is correct
9 Correct 119 ms 377700 KB Output is correct
10 Correct 125 ms 379568 KB Output is correct
11 Correct 127 ms 379436 KB Output is correct
12 Correct 128 ms 381520 KB Output is correct
13 Correct 124 ms 379984 KB Output is correct
14 Correct 131 ms 380156 KB Output is correct
15 Correct 143 ms 385900 KB Output is correct
16 Correct 147 ms 387412 KB Output is correct
17 Correct 138 ms 383916 KB Output is correct
18 Correct 130 ms 383828 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 408024 KB Output is correct
2 Correct 223 ms 404552 KB Output is correct
3 Correct 769 ms 512072 KB Output is correct
4 Correct 263 ms 416856 KB Output is correct
5 Correct 823 ms 580108 KB Output is correct
6 Correct 1060 ms 615768 KB Output is correct
7 Correct 133 ms 409476 KB Output is correct
8 Correct 138 ms 407892 KB Output is correct
9 Correct 121 ms 378432 KB Output is correct
10 Correct 122 ms 377680 KB Output is correct
11 Correct 144 ms 408568 KB Output is correct
12 Correct 125 ms 378696 KB Output is correct
13 Correct 217 ms 404564 KB Output is correct
14 Correct 183 ms 394672 KB Output is correct
15 Correct 176 ms 394108 KB Output is correct
16 Correct 165 ms 389716 KB Output is correct
17 Correct 413 ms 437312 KB Output is correct
18 Correct 332 ms 428116 KB Output is correct
19 Correct 265 ms 416852 KB Output is correct
20 Correct 268 ms 417368 KB Output is correct
21 Correct 493 ms 466640 KB Output is correct
22 Correct 817 ms 579920 KB Output is correct
23 Correct 637 ms 483204 KB Output is correct
24 Correct 497 ms 471032 KB Output is correct
25 Correct 1185 ms 536400 KB Output is correct
26 Runtime error 780 ms 1048576 KB Execution killed with signal 9
27 Correct 1062 ms 862704 KB Output is correct
28 Correct 1061 ms 615760 KB Output is correct
29 Correct 1057 ms 590440 KB Output is correct
30 Correct 1012 ms 661032 KB Output is correct
31 Correct 1388 ms 680904 KB Output is correct
32 Correct 1129 ms 902620 KB Output is correct