Submission #1072569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072569		redLotus31415	Tracks in the Snow (BOI13_tracks)	C++14	43.54 / 100	2103 ms	645200 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];
    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 (stderr)

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

• Subtask 1: 21.666666666666668 / 30
• Subtask 2: 21.875 / 70