oj.uz

Submission #971312

# Submission time Handle Problem Language Result Execution time Memory
971312 2024-04-28T11:09:09 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
67.1875 / 100
 1235 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];
unordered_set<int> graph[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]].count(component[i][j]) == 0) {
                graph[component[i + 1][j]].insert(component[i][j]);
                graph[component[i][j]].insert(component[i + 1][j]);
            }
            if(i - 1 >= 0 && meadow[i - 1][j] != '.' && component[i - 1][j] != component[i][j] && graph[component[i - 1][j]].count(component[i][j]) == 0) {
                graph[component[i - 1][j]].insert(component[i][j]);
                graph[component[i][j]].insert(component[i - 1][j]);
            }  
            if(j + 1 < w && meadow[i][j + 1] != '.' && component[i][j + 1] != component[i][j] && graph[component[i][j + 1]].count(component[i][j]) == 0) {
                graph[component[i][j + 1]].insert(component[i][j]);
                graph[component[i][j]].insert(component[i][j + 1]);
            }  
            if(j - 1 >= 0 && meadow[i][j - 1] != '.' && component[i][j - 1] != component[i][j] && graph[component[i][j - 1]].count(component[i][j]) == 0) {
                graph[component[i][j - 1]].insert(component[i][j]);
                graph[component[i][j]].insert(component[i][j - 1]);
            }     
        }
    }
    int d[cnt];
    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 490 ms 889936 KB Output is correct
2 Correct 355 ms 877600 KB Output is correct
3 Correct 350 ms 878060 KB Output is correct
4 Correct 362 ms 884396 KB Output is correct
5 Correct 359 ms 881488 KB Output is correct
6 Correct 353 ms 877908 KB Output is correct
7 Correct 350 ms 877928 KB Output is correct
8 Correct 351 ms 878284 KB Output is correct
9 Correct 353 ms 878528 KB Output is correct
10 Correct 355 ms 881232 KB Output is correct
11 Correct 348 ms 879956 KB Output is correct
12 Correct 368 ms 883264 KB Output is correct
13 Correct 361 ms 881716 KB Output is correct
14 Correct 391 ms 881472 KB Output is correct
15 Correct 379 ms 889684 KB Output is correct
16 Correct 387 ms 890064 KB Output is correct
17 Correct 369 ms 889120 KB Output is correct
18 Correct 358 ms 884036 KB Output is correct

Subtask #2
37.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 909440 KB Output is correct
2 Correct 488 ms 928560 KB Output is correct
3 Runtime error 762 ms 1048576 KB Execution killed with signal 9
4 Correct 548 ms 954616 KB Output is correct
5 Runtime error 608 ms 1048576 KB Execution killed with signal 9
6 Runtime error 1033 ms 1048576 KB Execution killed with signal 9
7 Correct 364 ms 910752 KB Output is correct
8 Correct 360 ms 909392 KB Output is correct
9 Correct 375 ms 879756 KB Output is correct
10 Correct 346 ms 878412 KB Output is correct
11 Correct 366 ms 909536 KB Output is correct
12 Correct 362 ms 880720 KB Output is correct
13 Correct 477 ms 928892 KB Output is correct
14 Correct 426 ms 908884 KB Output is correct
15 Correct 439 ms 915172 KB Output is correct
16 Correct 407 ms 899920 KB Output is correct
17 Correct 681 ms 1000272 KB Output is correct
18 Correct 708 ms 1008376 KB Output is correct
19 Correct 549 ms 954448 KB Output is correct
20 Correct 547 ms 961692 KB Output is correct
21 Runtime error 646 ms 1048576 KB Execution killed with signal 9
22 Runtime error 588 ms 1048576 KB Execution killed with signal 9
23 Runtime error 708 ms 1048576 KB Execution killed with signal 9
24 Runtime error 675 ms 1048576 KB Execution killed with signal 9
25 Runtime error 769 ms 1048576 KB Execution killed with signal 9
26 Runtime error 544 ms 1048576 KB Execution killed with signal 9
27 Runtime error 586 ms 1048576 KB Execution killed with signal 9
28 Runtime error 1006 ms 1048576 KB Execution killed with signal 9
29 Runtime error 1235 ms 1048576 KB Execution killed with signal 9
30 Runtime error 784 ms 1048576 KB Execution killed with signal 9
31 Runtime error 1030 ms 1048576 KB Execution killed with signal 9
32 Runtime error 612 ms 1048576 KB Execution killed with signal 9