oj.uz

Submission #1072580

# Submission time Handle Problem Language Result Execution time Memory
1072580 2024-08-23T22:40:42 Z redLotus31415 Tracks in the Snow (BOI13_tracks) C++14
43.5417 / 100
 2000 ms 817492 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 (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; 
    
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:25:10: warning: variable 'visited' set but not used [-Wunused-but-set-variable]
   25 |     bool visited[H][W];
      |          ^~~~~~~

Subtask #1
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 143132 KB Time limit exceeded
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 35 ms 2132 KB Output is correct
5 Correct 64 ms 3412 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 612 ms 16504 KB Output is correct
11 Correct 8 ms 860 KB Output is correct
12 Execution timed out 2097 ms 51256 KB Time limit exceeded
13 Correct 57 ms 3408 KB Output is correct
14 Correct 57 ms 3412 KB Output is correct
15 Execution timed out 2077 ms 79336 KB Time limit exceeded
16 Execution timed out 2044 ms 145844 KB Time limit exceeded
17 Execution timed out 2048 ms 80460 KB Time limit exceeded
18 Correct 34 ms 2088 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1884 KB Output is correct
2 Execution timed out 2092 ms 197604 KB Time limit exceeded
3 Execution timed out 2116 ms 443756 KB Time limit exceeded
4 Execution timed out 2019 ms 104532 KB Time limit exceeded
5 Execution timed out 2071 ms 817492 KB Time limit exceeded
6 Execution timed out 2021 ms 120096 KB Time limit exceeded
7 Correct 4 ms 1628 KB Output is correct
8 Correct 5 ms 1884 KB Output is correct
9 Execution timed out 2099 ms 99472 KB Time limit exceeded
10 Correct 3 ms 1112 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 7 ms 3060 KB Output is correct
13 Execution timed out 2071 ms 198112 KB Time limit exceeded
14 Execution timed out 2045 ms 234964 KB Time limit exceeded
15 Correct 166 ms 42132 KB Output is correct
16 Execution timed out 2112 ms 168116 KB Time limit exceeded
17 Execution timed out 2057 ms 201384 KB Time limit exceeded
18 Correct 694 ms 163120 KB Output is correct
19 Execution timed out 2075 ms 103580 KB Time limit exceeded
20 Execution timed out 2072 ms 175364 KB Time limit exceeded
21 Execution timed out 2108 ms 301356 KB Time limit exceeded
22 Execution timed out 2074 ms 804984 KB Time limit exceeded
23 Execution timed out 2051 ms 331860 KB Time limit exceeded
24 Correct 1282 ms 449784 KB Output is correct
25 Execution timed out 2027 ms 594812 KB Time limit exceeded
26 Correct 1603 ms 173092 KB Output is correct
27 Execution timed out 2008 ms 119424 KB Time limit exceeded
28 Execution timed out 2033 ms 120060 KB Time limit exceeded
29 Execution timed out 2080 ms 103188 KB Time limit exceeded
30 Execution timed out 2074 ms 121556 KB Time limit exceeded
31 Execution timed out 2058 ms 255652 KB Time limit exceeded
32 Execution timed out 2051 ms 132284 KB Time limit exceeded