oj.uz

Submission #971321

# Submission time Handle Problem Language Result Execution time Memory
971321 2024-04-28T11:15:51 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1311 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<pair<int, 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], 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 259 ms 387348 KB Output is correct
2 Correct 118 ms 377292 KB Output is correct
3 Correct 139 ms 377384 KB Output is correct
4 Correct 134 ms 383636 KB Output is correct
5 Correct 125 ms 380052 KB Output is correct
6 Correct 123 ms 377168 KB Output is correct
7 Correct 119 ms 377424 KB Output is correct
8 Correct 119 ms 377428 KB Output is correct
9 Correct 120 ms 377672 KB Output is correct
10 Correct 129 ms 379512 KB Output is correct
11 Correct 128 ms 379356 KB Output is correct
12 Correct 128 ms 381520 KB Output is correct
13 Correct 124 ms 380044 KB Output is correct
14 Correct 131 ms 380052 KB Output is correct
15 Correct 142 ms 385876 KB Output is correct
16 Correct 145 ms 387412 KB Output is correct
17 Correct 138 ms 384080 KB Output is correct
18 Correct 128 ms 383820 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 408016 KB Output is correct
2 Correct 228 ms 404548 KB Output is correct
3 Correct 742 ms 511984 KB Output is correct
4 Correct 257 ms 416844 KB Output is correct
5 Correct 787 ms 580872 KB Output is correct
6 Correct 1080 ms 615808 KB Output is correct
7 Correct 133 ms 409428 KB Output is correct
8 Correct 141 ms 408084 KB Output is correct
9 Correct 123 ms 378452 KB Output is correct
10 Correct 120 ms 377908 KB Output is correct
11 Correct 132 ms 408660 KB Output is correct
12 Correct 125 ms 378904 KB Output is correct
13 Correct 217 ms 404528 KB Output is correct
14 Correct 176 ms 394740 KB Output is correct
15 Correct 197 ms 394340 KB Output is correct
16 Correct 167 ms 389716 KB Output is correct
17 Correct 393 ms 437176 KB Output is correct
18 Correct 326 ms 428112 KB Output is correct
19 Correct 291 ms 416848 KB Output is correct
20 Correct 279 ms 417360 KB Output is correct
21 Correct 501 ms 466732 KB Output is correct
22 Correct 788 ms 580492 KB Output is correct
23 Correct 628 ms 483212 KB Output is correct
24 Correct 483 ms 471376 KB Output is correct
25 Correct 1160 ms 536536 KB Output is correct
26 Runtime error 718 ms 1048576 KB Execution killed with signal 9
27 Correct 1073 ms 862844 KB Output is correct
28 Correct 1080 ms 615668 KB Output is correct
29 Correct 1014 ms 590504 KB Output is correct
30 Correct 1041 ms 661316 KB Output is correct
31 Correct 1311 ms 680800 KB Output is correct
32 Correct 1193 ms 902588 KB Output is correct