oj.uz

Submission #1072579

# Submission time Handle Problem Language Result Execution time Memory
1072579 2024-08-23T22:37:40 Z redLotus31415 Tracks in the Snow (BOI13_tracks) C++14
43.5417 / 100
 2000 ms 801280 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <fstream>
#include <string>
#include <bits/stdc++.h> 
#include <numeric>
using namespace std;

#define FOR(i,L,R) for (int i = L; i < R; i++) //next four are for "for loops"
#define FOR_STEP(i,L,R, STEP) for (int i = L; i < R; i+= STEP) //next four are for "for loops"


struct coord {
    int x;
    int y;
};

int main(){
    int H, W;
    cin >> H >> W; 
    char array[H][W]; 
    int connected[H][W];
    bool visited[H][W];

    FOR(i, 0, H) {
        FOR(j, 0, W) {
            char x; cin >> x; 
            array[i][j] = x; 
            connected[i][j] = -1; 
            visited[i][j] = false; 
        }
    }

    int left[] = {-1, 1, 0, 0};
    int right[] = {0, 0, -1, 1}; 
    int count = -1; 
    stack<coord> DFSStack; 
    map<int, set<int>> components; 

    FOR(i, 0, H) {
        FOR(j, 0, W) {
            if (!visited[i][j] && array[i][j] != '.') {count++; DFSStack.push({i,j});}
            while (!DFSStack.empty()) {
                coord topCoord = DFSStack.top();
                DFSStack.pop();
                visited[topCoord.x][topCoord.y] = true; 
                connected[topCoord.x][topCoord.y]= count; 
                FOR (k, 0, 4) {
                    int nx = topCoord.x + left[k];
                    int ny = topCoord.y + right[k];
                    if (0 <= nx && nx < H && 0<= ny && ny < W) {
                        if (!visited[nx][ny] && array[nx][ny] == array[topCoord.x][topCoord.y]) DFSStack.push({nx, ny}); 
                        else {
                            if (connected[nx][ny] != -1) {
                                components[count].insert(connected[nx][ny]); 
                                components[connected[nx][ny]].insert(count); 
                            }
                        }
                    }
                }
            }
        }
    }

    
    queue<coord> BFSQ; 
    // node and depth 
    BFSQ.push({0, 0});
    unordered_map<int, bool> BFSVisited; 
    int maxDepth = 0; 
    while (!BFSQ.empty()) {
        coord top = BFSQ.front();
        BFSQ.pop();  
        BFSVisited[top.x] = true; 
        maxDepth = max(maxDepth, top.y); 
        for (auto const&neighbor: components[top.x]) {
            if (!BFSVisited[neighbor]) {
                BFSQ.push({neighbor, top.y+1});
            }
        }
    }

    cout << maxDepth+1; 
    
}

Subtask #1
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2048 ms 145584 KB Time limit exceeded
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 32 ms 2004 KB Output is correct
5 Correct 73 ms 3388 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 599 ms 16472 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Execution timed out 2093 ms 51136 KB Time limit exceeded
13 Correct 55 ms 3384 KB Output is correct
14 Correct 87 ms 3152 KB Output is correct
15 Execution timed out 2020 ms 79908 KB Time limit exceeded
16 Execution timed out 2073 ms 152172 KB Time limit exceeded
17 Execution timed out 2056 ms 80060 KB Time limit exceeded
18 Correct 32 ms 1876 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1880 KB Output is correct
2 Execution timed out 2101 ms 181600 KB Time limit exceeded
3 Execution timed out 2112 ms 435572 KB Time limit exceeded
4 Execution timed out 2050 ms 101212 KB Time limit exceeded
5 Execution timed out 2102 ms 801280 KB Time limit exceeded
6 Execution timed out 2033 ms 128244 KB Time limit exceeded
7 Correct 7 ms 1624 KB Output is correct
8 Correct 5 ms 1884 KB Output is correct
9 Execution timed out 2099 ms 86564 KB Time limit exceeded
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1212 KB Output is correct
12 Correct 8 ms 3160 KB Output is correct
13 Execution timed out 2080 ms 195532 KB Time limit exceeded
14 Execution timed out 2036 ms 243212 KB Time limit exceeded
15 Correct 172 ms 42920 KB Output is correct
16 Execution timed out 2071 ms 172892 KB Time limit exceeded
17 Execution timed out 2025 ms 203028 KB Time limit exceeded
18 Correct 737 ms 165312 KB Output is correct
19 Execution timed out 2019 ms 104576 KB Time limit exceeded
20 Execution timed out 2045 ms 180356 KB Time limit exceeded
21 Execution timed out 2020 ms 294452 KB Time limit exceeded
22 Execution timed out 2075 ms 768756 KB Time limit exceeded
23 Execution timed out 2032 ms 331516 KB Time limit exceeded
24 Correct 1348 ms 454288 KB Output is correct
25 Execution timed out 2122 ms 607160 KB Time limit exceeded
26 Correct 1553 ms 178636 KB Output is correct
27 Execution timed out 2104 ms 127696 KB Time limit exceeded
28 Execution timed out 2088 ms 131316 KB Time limit exceeded
29 Execution timed out 2063 ms 110236 KB Time limit exceeded
30 Execution timed out 2024 ms 126528 KB Time limit exceeded
31 Execution timed out 2040 ms 252212 KB Time limit exceeded
32 Execution timed out 2025 ms 140092 KB Time limit exceeded