oj.uz

Submission #971309

# Submission time Handle Problem Language Result Execution time Memory
971309 2024-04-28T11:07:44 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
86.875 / 100
 1766 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() {
    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 445 ms 762704 KB Output is correct
2 Correct 288 ms 752212 KB Output is correct
3 Correct 275 ms 752576 KB Output is correct
4 Correct 279 ms 758424 KB Output is correct
5 Correct 271 ms 755776 KB Output is correct
6 Correct 274 ms 752440 KB Output is correct
7 Correct 273 ms 752716 KB Output is correct
8 Correct 265 ms 752608 KB Output is correct
9 Correct 272 ms 752972 KB Output is correct
10 Correct 272 ms 755404 KB Output is correct
11 Correct 292 ms 754516 KB Output is correct
12 Correct 276 ms 756820 KB Output is correct
13 Correct 269 ms 755764 KB Output is correct
14 Correct 286 ms 755796 KB Output is correct
15 Correct 333 ms 762068 KB Output is correct
16 Correct 298 ms 762576 KB Output is correct
17 Correct 283 ms 761424 KB Output is correct
18 Correct 280 ms 758608 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 783680 KB Output is correct
2 Correct 371 ms 789456 KB Output is correct
3 Correct 997 ms 972820 KB Output is correct
4 Correct 435 ms 810368 KB Output is correct
5 Runtime error 651 ms 1048576 KB Execution killed with signal 9
6 Correct 1476 ms 946576 KB Output is correct
7 Correct 280 ms 785060 KB Output is correct
8 Correct 285 ms 783856 KB Output is correct
9 Correct 269 ms 753744 KB Output is correct
10 Correct 271 ms 752932 KB Output is correct
11 Correct 276 ms 784196 KB Output is correct
12 Correct 268 ms 754516 KB Output is correct
13 Correct 370 ms 788232 KB Output is correct
14 Correct 352 ms 774848 KB Output is correct
15 Correct 346 ms 777896 KB Output is correct
16 Correct 311 ms 768004 KB Output is correct
17 Correct 546 ms 835676 KB Output is correct
18 Correct 507 ms 837656 KB Output is correct
19 Correct 440 ms 808320 KB Output is correct
20 Correct 432 ms 809308 KB Output is correct
21 Correct 733 ms 888428 KB Output is correct
22 Runtime error 623 ms 1048576 KB Execution killed with signal 9
23 Correct 760 ms 902012 KB Output is correct
24 Correct 677 ms 939264 KB Output is correct
25 Runtime error 845 ms 1048576 KB Execution killed with signal 9
26 Runtime error 560 ms 1048576 KB Execution killed with signal 9
27 Runtime error 600 ms 1048576 KB Execution killed with signal 9
28 Correct 1440 ms 946568 KB Output is correct
29 Correct 1318 ms 913400 KB Output is correct
30 Correct 1337 ms 999588 KB Output is correct
31 Correct 1766 ms 1036376 KB Output is correct
32 Runtime error 657 ms 1048576 KB Execution killed with signal 9