oj.uz

Submission #971317

# Submission time Handle Problem Language Result Execution time Memory
971317 2024-04-28T11:11:05 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 1416 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];
vector<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]].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]);
            }     
        }
    }
    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 210 ms 386560 KB Output is correct
2 Correct 122 ms 376508 KB Output is correct
3 Correct 123 ms 376712 KB Output is correct
4 Correct 130 ms 383148 KB Output is correct
5 Correct 132 ms 379168 KB Output is correct
6 Correct 118 ms 376464 KB Output is correct
7 Correct 126 ms 376772 KB Output is correct
8 Correct 120 ms 376780 KB Output is correct
9 Correct 120 ms 377188 KB Output is correct
10 Correct 123 ms 378956 KB Output is correct
11 Correct 128 ms 378596 KB Output is correct
12 Correct 137 ms 380952 KB Output is correct
13 Correct 126 ms 379216 KB Output is correct
14 Correct 125 ms 379552 KB Output is correct
15 Correct 145 ms 384980 KB Output is correct
16 Correct 149 ms 386640 KB Output is correct
17 Correct 140 ms 383252 KB Output is correct
18 Correct 144 ms 383316 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 407288 KB Output is correct
2 Correct 225 ms 403536 KB Output is correct
3 Correct 794 ms 519188 KB Output is correct
4 Correct 270 ms 415940 KB Output is correct
5 Correct 864 ms 587664 KB Output is correct
6 Correct 1177 ms 621416 KB Output is correct
7 Correct 138 ms 408656 KB Output is correct
8 Correct 138 ms 407356 KB Output is correct
9 Correct 125 ms 377680 KB Output is correct
10 Correct 123 ms 376916 KB Output is correct
11 Correct 135 ms 408128 KB Output is correct
12 Correct 124 ms 377776 KB Output is correct
13 Correct 233 ms 403540 KB Output is correct
14 Correct 181 ms 393612 KB Output is correct
15 Correct 175 ms 393184 KB Output is correct
16 Correct 174 ms 388856 KB Output is correct
17 Correct 389 ms 435796 KB Output is correct
18 Correct 349 ms 427372 KB Output is correct
19 Correct 269 ms 415824 KB Output is correct
20 Correct 275 ms 416272 KB Output is correct
21 Correct 512 ms 470264 KB Output is correct
22 Correct 840 ms 587636 KB Output is correct
23 Correct 655 ms 486068 KB Output is correct
24 Correct 519 ms 474416 KB Output is correct
25 Correct 1231 ms 543472 KB Output is correct
26 Runtime error 743 ms 1048576 KB Execution killed with signal 9
27 Correct 1122 ms 870472 KB Output is correct
28 Correct 1153 ms 621656 KB Output is correct
29 Correct 1043 ms 596696 KB Output is correct
30 Correct 1056 ms 667624 KB Output is correct
31 Correct 1416 ms 684896 KB Output is correct
32 Correct 1304 ms 909948 KB Output is correct