oj.uz

Submission #971299

# Submission time Handle Problem Language Result Execution time Memory
971299 2024-04-28T11:00:05 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
17.6042 / 100
 1920 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];

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++;
            }
        }
    }
    unordered_set<int> graph[cnt];
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(i + 1 < h && 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 && 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 && 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 && 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
6.66666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 17232 KB Output isn't correct
2 Incorrect 1 ms 2648 KB Output isn't correct
3 Incorrect 1 ms 2652 KB Output isn't correct
4 Correct 12 ms 9052 KB Output is correct
5 Incorrect 9 ms 6236 KB Output isn't correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Incorrect 1 ms 2648 KB Output isn't correct
8 Correct 1 ms 2652 KB Output is correct
9 Incorrect 2 ms 2908 KB Output isn't correct
10 Incorrect 7 ms 5976 KB Output isn't correct
11 Correct 4 ms 3932 KB Output is correct
12 Incorrect 13 ms 9560 KB Output isn't correct
13 Incorrect 10 ms 6492 KB Output isn't correct
14 Incorrect 8 ms 6416 KB Output isn't correct
15 Incorrect 33 ms 18348 KB Output isn't correct
16 Incorrect 35 ms 17236 KB Output isn't correct
17 Incorrect 31 ms 18688 KB Output isn't correct
18 Correct 10 ms 9048 KB Output is correct

Subtask #2
10.9375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 34140 KB Output isn't correct
2 Incorrect 168 ms 78788 KB Output isn't correct
3 Incorrect 1109 ms 526708 KB Output isn't correct
4 Incorrect 270 ms 112044 KB Output isn't correct
5 Runtime error 1391 ms 1048576 KB Execution killed with signal 9
6 Correct 1118 ms 241880 KB Output is correct
7 Incorrect 14 ms 34396 KB Output isn't correct
8 Incorrect 13 ms 33884 KB Output isn't correct
9 Incorrect 6 ms 4952 KB Output isn't correct
10 Incorrect 3 ms 3676 KB Output isn't correct
11 Incorrect 11 ms 33628 KB Output isn't correct
12 Incorrect 5 ms 6492 KB Output isn't correct
13 Incorrect 165 ms 77692 KB Output isn't correct
14 Incorrect 90 ms 48532 KB Output isn't correct
15 Incorrect 111 ms 58808 KB Output isn't correct
16 Incorrect 74 ms 35424 KB Output isn't correct
17 Incorrect 399 ms 189628 KB Output isn't correct
18 Incorrect 460 ms 206028 KB Output isn't correct
19 Incorrect 289 ms 111844 KB Output isn't correct
20 Incorrect 258 ms 126488 KB Output isn't correct
21 Incorrect 728 ms 320764 KB Output isn't correct
22 Runtime error 1215 ms 1048576 KB Execution killed with signal 9
23 Incorrect 787 ms 352272 KB Output isn't correct
24 Incorrect 894 ms 526496 KB Output isn't correct
25 Incorrect 1920 ms 804452 KB Output isn't correct
26 Runtime error 806 ms 1048576 KB Execution killed with signal 9
27 Correct 928 ms 498608 KB Output is correct
28 Correct 1118 ms 241892 KB Output is correct
29 Correct 929 ms 189728 KB Output is correct
30 Correct 973 ms 268808 KB Output is correct
31 Incorrect 1785 ms 449192 KB Output isn't correct
32 Incorrect 1073 ms 563928 KB Output isn't correct