oj.uz

Submission #971288

# Submission time Handle Problem Language Result Execution time Memory
971288 2024-04-28T10:49:48 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
15.4167 / 100
 1816 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];
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() {
    cin >> h >> w;
    for(int i = 0; i < h; i++) {
        string tmps;
        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(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 = 0;
    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 476 ms 763040 KB Output isn't correct
2 Incorrect 287 ms 752464 KB Output isn't correct
3 Incorrect 283 ms 752724 KB Output isn't correct
4 Correct 324 ms 758412 KB Output is correct
5 Incorrect 293 ms 756556 KB Output isn't correct
6 Incorrect 292 ms 752248 KB Output isn't correct
7 Incorrect 287 ms 752720 KB Output isn't correct
8 Correct 289 ms 752864 KB Output is correct
9 Incorrect 301 ms 753232 KB Output isn't correct
10 Incorrect 303 ms 756308 KB Output isn't correct
11 Correct 287 ms 754516 KB Output is correct
12 Incorrect 299 ms 757272 KB Output isn't correct
13 Incorrect 309 ms 756612 KB Output isn't correct
14 Incorrect 295 ms 756564 KB Output isn't correct
15 Incorrect 327 ms 764300 KB Output isn't correct
16 Incorrect 320 ms 763084 KB Output isn't correct
17 Incorrect 338 ms 765228 KB Output isn't correct
18 Correct 296 ms 758380 KB Output is correct

Subtask #2
8.75 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 784060 KB Output isn't correct
2 Incorrect 494 ms 807760 KB Output isn't correct
3 Runtime error 1467 ms 1048576 KB Execution killed with signal 9
4 Incorrect 742 ms 840588 KB Output isn't correct
5 Runtime error 977 ms 1048576 KB Execution killed with signal 9
6 Correct 1471 ms 962232 KB Output is correct
7 Incorrect 292 ms 785444 KB Output isn't correct
8 Incorrect 308 ms 784244 KB Output isn't correct
9 Incorrect 300 ms 754444 KB Output isn't correct
10 Incorrect 276 ms 753392 KB Output isn't correct
11 Incorrect 303 ms 784472 KB Output isn't correct
12 Incorrect 289 ms 755792 KB Output isn't correct
13 Incorrect 466 ms 807712 KB Output isn't correct
14 Incorrect 379 ms 786512 KB Output isn't correct
15 Incorrect 410 ms 793388 KB Output isn't correct
16 Incorrect 364 ms 776036 KB Output isn't correct
17 Incorrect 825 ms 887580 KB Output isn't correct
18 Incorrect 810 ms 897644 KB Output isn't correct
19 Incorrect 590 ms 837320 KB Output isn't correct
20 Incorrect 627 ms 845264 KB Output isn't correct
21 Incorrect 1106 ms 983108 KB Output isn't correct
22 Runtime error 983 ms 1048576 KB Execution killed with signal 9
23 Incorrect 1200 ms 1001196 KB Output isn't correct
24 Runtime error 1157 ms 1048576 KB Execution killed with signal 9
25 Runtime error 1289 ms 1048576 KB Execution killed with signal 9
26 Runtime error 592 ms 1048576 KB Execution killed with signal 9
27 Runtime error 606 ms 1048576 KB Execution killed with signal 9
28 Correct 1473 ms 962276 KB Output is correct
29 Correct 1388 ms 928672 KB Output is correct
30 Correct 1306 ms 1014632 KB Output is correct
31 Incorrect 1816 ms 1048576 KB Output isn't correct
32 Runtime error 624 ms 1048576 KB Execution killed with signal 9