oj.uz

Submission #1072586

# Submission time Handle Problem Language Result Execution time Memory
1072586 2024-08-23T22:49:14 Z redLotus31415 Tracks in the Snow (BOI13_tracks) C++14
43.0208 / 100
 2000 ms 1048576 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; 
    unordered_map<int, unordered_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.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 197200 KB Time limit exceeded
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 24 ms 2180 KB Output is correct
5 Correct 43 ms 3872 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 434 ms 16788 KB Output is correct
11 Correct 8 ms 856 KB Output is correct
12 Correct 1364 ms 47540 KB Output is correct
13 Correct 43 ms 3676 KB Output is correct
14 Correct 42 ms 3632 KB Output is correct
15 Execution timed out 2035 ms 138768 KB Time limit exceeded
16 Execution timed out 2102 ms 196840 KB Time limit exceeded
17 Execution timed out 2060 ms 108832 KB Time limit exceeded
18 Correct 25 ms 2128 KB Output is correct

Subtask #2
19.6875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2432 KB Output is correct
2 Execution timed out 2086 ms 255508 KB Time limit exceeded
3 Execution timed out 2086 ms 600572 KB Time limit exceeded
4 Execution timed out 2059 ms 146064 KB Time limit exceeded
5 Runtime error 1441 ms 1048576 KB Execution killed with signal 9
6 Execution timed out 2052 ms 177356 KB Time limit exceeded
7 Correct 5 ms 1880 KB Output is correct
8 Correct 5 ms 2260 KB Output is correct
9 Execution timed out 2047 ms 172160 KB Time limit exceeded
10 Correct 3 ms 1372 KB Output is correct
11 Correct 3 ms 1372 KB Output is correct
12 Correct 6 ms 3980 KB Output is correct
13 Execution timed out 2107 ms 250468 KB Time limit exceeded
14 Execution timed out 2055 ms 292680 KB Time limit exceeded
15 Correct 142 ms 51140 KB Output is correct
16 Execution timed out 2083 ms 188152 KB Time limit exceeded
17 Execution timed out 2076 ms 284348 KB Time limit exceeded
18 Correct 615 ms 198752 KB Output is correct
19 Execution timed out 2051 ms 138364 KB Time limit exceeded
20 Execution timed out 2077 ms 284356 KB Time limit exceeded
21 Execution timed out 2071 ms 372468 KB Time limit exceeded
22 Runtime error 1489 ms 1048576 KB Execution killed with signal 9
23 Execution timed out 2067 ms 447228 KB Time limit exceeded
24 Correct 1172 ms 554184 KB Output is correct
25 Execution timed out 2099 ms 770252 KB Time limit exceeded
26 Execution timed out 2057 ms 172040 KB Time limit exceeded
27 Execution timed out 2092 ms 118228 KB Time limit exceeded
28 Execution timed out 2063 ms 169356 KB Time limit exceeded
29 Execution timed out 2045 ms 136404 KB Time limit exceeded
30 Execution timed out 2060 ms 125300 KB Time limit exceeded
31 Execution timed out 2099 ms 517748 KB Time limit exceeded
32 Execution timed out 2009 ms 130996 KB Time limit exceeded