oj.uz

Submission #971327

# Submission time Handle Problem Language Result Execution time Memory
971327 2024-04-28T11:21:37 Z Bodisha Tracks in the Snow (BOI13_tracks) C++17
86.875 / 100
 2000 ms 1048576 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];
set<pair<int, int>> edges;
queue<int> q;

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] && edges.count({component[i][j], component[i + 1][j]}) == 0) {
                graph[component[i + 1][j]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i + 1][j]);
                edges.insert({component[i + 1][j], component[i][j]});
                edges.insert({component[i][j], component[i + 1][j]});
            }
            if(i - 1 >= 0 && meadow[i - 1][j] != '.' && component[i - 1][j] != component[i][j] && edges.count({component[i][j], component[i - 1][j]}) == 0) {
                graph[component[i - 1][j]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i - 1][j]);
                edges.insert({component[i - 1][j], component[i][j]});
                edges.insert({component[i][j], component[i - 1][j]});
            }  
            if(j + 1 < w && meadow[i][j + 1] != '.' && component[i][j + 1] != component[i][j] && edges.count({component[i][j], component[i][j + 1]}) == 0) {
                graph[component[i][j + 1]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i][j + 1]);
                edges.insert({component[i][j], component[i][j + 1]});
                edges.insert({component[i][j + 1], component[i][j]});
            }  
            if(j - 1 >= 0 && meadow[i][j - 1] != '.' && component[i][j - 1] != component[i][j] && edges.count({component[i][j], component[i][j - 1]}) == 0) {
                graph[component[i][j - 1]].push_back(component[i][j]);
                graph[component[i][j]].push_back(component[i][j - 1]);
                edges.insert({component[i][j], component[i][j - 1]});
                edges.insert({component[i][j - 1], component[i][j]});
            }     
        }
    }
    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 292 ms 388952 KB Output is correct
2 Correct 122 ms 377172 KB Output is correct
3 Correct 121 ms 377428 KB Output is correct
4 Correct 134 ms 383184 KB Output is correct
5 Correct 135 ms 380784 KB Output is correct
6 Correct 118 ms 377024 KB Output is correct
7 Correct 118 ms 377512 KB Output is correct
8 Correct 118 ms 377532 KB Output is correct
9 Correct 122 ms 378196 KB Output is correct
10 Correct 125 ms 380240 KB Output is correct
11 Correct 121 ms 379220 KB Output is correct
12 Correct 141 ms 382032 KB Output is correct
13 Correct 134 ms 380704 KB Output is correct
14 Correct 126 ms 380720 KB Output is correct
15 Correct 175 ms 387940 KB Output is correct
16 Correct 195 ms 388436 KB Output is correct
17 Correct 164 ms 387408 KB Output is correct
18 Correct 137 ms 383316 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 408632 KB Output is correct
2 Correct 342 ms 419872 KB Output is correct
3 Correct 1471 ms 635744 KB Output is correct
4 Correct 407 ms 441656 KB Output is correct
5 Execution timed out 2051 ms 870516 KB Time limit exceeded
6 Execution timed out 2050 ms 591444 KB Time limit exceeded
7 Correct 138 ms 410424 KB Output is correct
8 Correct 136 ms 408656 KB Output is correct
9 Correct 125 ms 378900 KB Output is correct
10 Correct 129 ms 377884 KB Output is correct
11 Correct 146 ms 408916 KB Output is correct
12 Correct 125 ms 379776 KB Output is correct
13 Correct 373 ms 419692 KB Output is correct
14 Correct 244 ms 403736 KB Output is correct
15 Correct 268 ms 407356 KB Output is correct
16 Correct 228 ms 395808 KB Output is correct
17 Correct 691 ms 477448 KB Output is correct
18 Correct 832 ms 480324 KB Output is correct
19 Correct 406 ms 441424 KB Output is correct
20 Correct 425 ms 444960 KB Output is correct
21 Correct 921 ms 540784 KB Output is correct
22 Execution timed out 2121 ms 907280 KB Time limit exceeded
23 Correct 1236 ms 559140 KB Output is correct
24 Correct 1086 ms 611720 KB Output is correct
25 Execution timed out 2097 ms 651488 KB Time limit exceeded
26 Runtime error 669 ms 1048576 KB Execution killed with signal 9
27 Correct 1074 ms 859168 KB Output is correct
28 Correct 1888 ms 591480 KB Output is correct
29 Correct 1581 ms 550100 KB Output is correct
30 Correct 1394 ms 632484 KB Output is correct
31 Execution timed out 2119 ms 594780 KB Time limit exceeded
32 Correct 1277 ms 910940 KB Output is correct