oj.uz

Submission #1072569

# Submission time Handle Problem Language Result Execution time Memory
1072569 2024-08-23T22:30:04 Z redLotus31415 Tracks in the Snow (BOI13_tracks) C++14
43.5417 / 100
 2000 ms 645200 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; 
    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 && !visited[nx][ny]) {
                        if (array[nx][ny] == array[topCoord.x][topCoord.y]) DFSStack.push({nx, ny}); 
                    }
                }
            }
        }
    }

    map<int, set<int>> components; 
    FOR(i, 0, H) {
        FOR (j, 0, W) {
            FOR (k, 0, 4) {
                int nx = i + left[k];
                int ny = j + right[k];
                if (0 <= nx && nx < H && 0<= ny && ny < W) {
                    if (connected[i][j] != -1) {
                        components[connected[i][j]].insert(connected[nx][ny]); 
                    }
                }
            }

        } 
    }

    int BFSDepth = 0;
    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; 
    
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:75:9: warning: unused variable 'BFSDepth' [-Wunused-variable]
   75 |     int BFSDepth = 0;
      |         ^~~~~~~~

Subtask #1
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2033 ms 146436 KB Time limit exceeded
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 26 ms 2216 KB Output is correct
5 Correct 66 ms 3664 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 548 KB Output is correct
10 Correct 665 ms 16872 KB Output is correct
11 Correct 7 ms 848 KB Output is correct
12 Execution timed out 2020 ms 51320 KB Time limit exceeded
13 Correct 68 ms 3824 KB Output is correct
14 Correct 66 ms 3676 KB Output is correct
15 Execution timed out 2029 ms 72472 KB Time limit exceeded
16 Execution timed out 2096 ms 146800 KB Time limit exceeded
17 Execution timed out 2067 ms 79936 KB Time limit exceeded
18 Correct 26 ms 2088 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2140 KB Output is correct
2 Execution timed out 2103 ms 184380 KB Time limit exceeded
3 Execution timed out 2057 ms 499888 KB Time limit exceeded
4 Execution timed out 2028 ms 114780 KB Time limit exceeded
5 Execution timed out 2056 ms 618948 KB Time limit exceeded
6 Execution timed out 2069 ms 155044 KB Time limit exceeded
7 Correct 5 ms 1880 KB Output is correct
8 Correct 6 ms 2252 KB Output is correct
9 Execution timed out 2101 ms 50876 KB Time limit exceeded
10 Correct 3 ms 1368 KB Output is correct
11 Correct 4 ms 1372 KB Output is correct
12 Correct 7 ms 3500 KB Output is correct
13 Execution timed out 2093 ms 202448 KB Time limit exceeded
14 Execution timed out 2084 ms 239628 KB Time limit exceeded
15 Correct 199 ms 49608 KB Output is correct
16 Execution timed out 2083 ms 171964 KB Time limit exceeded
17 Execution timed out 2032 ms 221892 KB Time limit exceeded
18 Correct 881 ms 192704 KB Output is correct
19 Execution timed out 2041 ms 115808 KB Time limit exceeded
20 Execution timed out 2071 ms 178276 KB Time limit exceeded
21 Execution timed out 2075 ms 320796 KB Time limit exceeded
22 Execution timed out 2062 ms 645200 KB Time limit exceeded
23 Execution timed out 2064 ms 377600 KB Time limit exceeded
24 Correct 1839 ms 528816 KB Output is correct
25 Execution timed out 2033 ms 608596 KB Time limit exceeded
26 Correct 1050 ms 184408 KB Output is correct
27 Execution timed out 2054 ms 135180 KB Time limit exceeded
28 Execution timed out 2071 ms 151568 KB Time limit exceeded
29 Execution timed out 2029 ms 133092 KB Time limit exceeded
30 Execution timed out 2054 ms 134740 KB Time limit exceeded
31 Execution timed out 2049 ms 258128 KB Time limit exceeded
32 Execution timed out 2025 ms 147644 KB Time limit exceeded