oj.uz

Submission #971341

# Submission time Handle Problem Language Result Execution time Memory
971341 2024-04-28T11:35:13 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1426 ms 679992 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<int> q;

void floodfill(int x, int y, int cmp) {
    stack<pair<int, int>> s;
    component[x][y] = cmp;
    s.push({x, y});
    while(!s.empty()) {
        pair<int, int> curr = s.top();
        s.pop();
        if(curr.first + 1 < h && meadow[curr.first][curr.second] == meadow[curr.first + 1][curr.second] && component[curr.first + 1][curr.second] == 0) {
            component[curr.first + 1][curr.second] = cmp;
            s.push({curr.first + 1, curr.second});
        }
        if(curr.first - 1 >= 0 && meadow[curr.first][curr.second] == meadow[curr.first - 1][curr.second] && component[curr.first - 1][curr.second] == 0) {
            component[curr.first - 1][curr.second] = cmp;
            s.push({curr.first - 1, curr.second});
        }
        if(curr.second + 1 < w && meadow[curr.first][curr.second] == meadow[curr.first][curr.second + 1] && component[curr.first][curr.second + 1] == 0) {
            component[curr.first][curr.second + 1] = cmp;
            s.push({curr.first, curr.second + 1});
        }
        if(curr.second - 1 >= 0 && meadow[curr.first][curr.second] == meadow[curr.first][curr.second - 1] && component[curr.first][curr.second - 1] == 0) {
            component[curr.first][curr.second - 1] = cmp;
            s.push({curr.first, curr.second - 1});
        }
    }
}

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]);
    while(!q.empty()) {
        int curr_node = q.front();
        q.pop();
        for(auto iter : graph[curr_node]) {
            if(d[iter] == -1) {
                d[iter] = d[curr_node] + 1;
                q.push(iter);
            }
        }
    }
    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 241 ms 387156 KB Output is correct
2 Correct 110 ms 377168 KB Output is correct
3 Correct 109 ms 377256 KB Output is correct
4 Correct 121 ms 382412 KB Output is correct
5 Correct 115 ms 380192 KB Output is correct
6 Correct 120 ms 377168 KB Output is correct
7 Correct 111 ms 377228 KB Output is correct
8 Correct 113 ms 377604 KB Output is correct
9 Correct 114 ms 377940 KB Output is correct
10 Correct 116 ms 379588 KB Output is correct
11 Correct 113 ms 378964 KB Output is correct
12 Correct 122 ms 381524 KB Output is correct
13 Correct 115 ms 379960 KB Output is correct
14 Correct 113 ms 379960 KB Output is correct
15 Correct 137 ms 385668 KB Output is correct
16 Correct 140 ms 387132 KB Output is correct
17 Correct 130 ms 383912 KB Output is correct
18 Correct 122 ms 382280 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 407376 KB Output is correct
2 Correct 220 ms 404048 KB Output is correct
3 Correct 802 ms 510884 KB Output is correct
4 Correct 263 ms 416536 KB Output is correct
5 Correct 897 ms 579852 KB Output is correct
6 Correct 1052 ms 554164 KB Output is correct
7 Correct 127 ms 408916 KB Output is correct
8 Correct 127 ms 407376 KB Output is correct
9 Correct 115 ms 377680 KB Output is correct
10 Correct 113 ms 377012 KB Output is correct
11 Correct 129 ms 408140 KB Output is correct
12 Correct 121 ms 378576 KB Output is correct
13 Correct 221 ms 404032 KB Output is correct
14 Correct 176 ms 394312 KB Output is correct
15 Correct 176 ms 393964 KB Output is correct
16 Correct 168 ms 389456 KB Output is correct
17 Correct 437 ms 436580 KB Output is correct
18 Correct 358 ms 427760 KB Output is correct
19 Correct 277 ms 416508 KB Output is correct
20 Correct 287 ms 417620 KB Output is correct
21 Correct 534 ms 465860 KB Output is correct
22 Correct 933 ms 579864 KB Output is correct
23 Correct 678 ms 481964 KB Output is correct
24 Correct 561 ms 472712 KB Output is correct
25 Correct 1234 ms 535304 KB Output is correct
26 Correct 651 ms 507476 KB Output is correct
27 Correct 707 ms 478128 KB Output is correct
28 Correct 1063 ms 553808 KB Output is correct
29 Correct 985 ms 539476 KB Output is correct
30 Correct 887 ms 513316 KB Output is correct
31 Correct 1426 ms 679992 KB Output is correct
32 Correct 682 ms 470408 KB Output is correct