Submission #1072599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072599		redLotus31415	Tracks in the Snow (BOI13_tracks)	C++17	45.21 / 100	2105 ms	1048576 KiB

tracks

    #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];
     
        FOR(i, 0, H) {
            FOR(j, 0, W) {
                char x; cin >> x; 
                array[i][j] = x; 
                connected[i][j] = -1; 
            }
        }
     
        int left[] = {-1, 1, 0, 0};
        int right[] = {0, 0, -1, 1}; 
        int count = -1; 
        stack<coord> DFSStack; 
        unordered_map<int, set<int>> components; 
     
        FOR(i, 0, H) {
            FOR(j, 0, W) {
                if (array[i][j] != '.') {count++; DFSStack.push({i,j});}
                while (!DFSStack.empty()) {
                    coord topCoord = DFSStack.top();
                    DFSStack.pop();
                    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 (array[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); 
                                }
                            }
                        }
                    }
                    array[topCoord.x][topCoord.y] = '.'; 
                }
            }
        }
     
        
        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: 23.333333333333332 / 30
• Subtask 2: 21.875 / 70