oj.uz

Submission #1072581

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

    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; 
    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
21.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2073 ms 149528 KB Time limit exceeded
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 35 ms 1880 KB Output is correct
5 Correct 57 ms 3160 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 448 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 578 ms 16600 KB Output is correct
11 Correct 7 ms 856 KB Output is correct
12 Execution timed out 2076 ms 51056 KB Time limit exceeded
13 Correct 56 ms 3164 KB Output is correct
14 Correct 68 ms 3152 KB Output is correct
15 Execution timed out 2074 ms 81128 KB Time limit exceeded
16 Execution timed out 2031 ms 144448 KB Time limit exceeded
17 Execution timed out 2054 ms 80268 KB Time limit exceeded
18 Correct 33 ms 1772 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 2068 ms 190924 KB Time limit exceeded
3 Execution timed out 2044 ms 417280 KB Time limit exceeded
4 Execution timed out 2080 ms 100060 KB Time limit exceeded
5 Execution timed out 2070 ms 791632 KB Time limit exceeded
6 Execution timed out 2045 ms 106060 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 2104 ms 92384 KB Time limit exceeded
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 7 ms 3164 KB Output is correct
13 Execution timed out 2104 ms 195724 KB Time limit exceeded
14 Execution timed out 2029 ms 243228 KB Time limit exceeded
15 Correct 151 ms 41156 KB Output is correct
16 Execution timed out 2051 ms 173744 KB Time limit exceeded
17 Execution timed out 2074 ms 200316 KB Time limit exceeded
18 Correct 691 ms 159096 KB Output is correct
19 Execution timed out 2060 ms 99928 KB Time limit exceeded
20 Execution timed out 2033 ms 177808 KB Time limit exceeded
21 Execution timed out 2057 ms 292252 KB Time limit exceeded
22 Execution timed out 2101 ms 845880 KB Time limit exceeded
23 Execution timed out 2079 ms 323660 KB Time limit exceeded
24 Correct 1228 ms 440836 KB Output is correct
25 Execution timed out 2093 ms 599228 KB Time limit exceeded
26 Correct 1455 ms 161168 KB Output is correct
27 Execution timed out 2041 ms 103824 KB Time limit exceeded
28 Execution timed out 2069 ms 107512 KB Time limit exceeded
29 Execution timed out 2071 ms 88288 KB Time limit exceeded
30 Execution timed out 2044 ms 106260 KB Time limit exceeded
31 Execution timed out 2064 ms 243288 KB Time limit exceeded
32 Execution timed out 2098 ms 116348 KB Time limit exceeded