oj.uz

Submission #1072583

# Submission time Handle Problem Language Result Execution time Memory
1072583 2024-08-23T22:43:19 Z redLotus31415 Tracks in the Snow (BOI13_tracks) C++14
45.2083 / 100
 2000 ms 1048580 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, 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 2028 ms 167084 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 1884 KB Output is correct
5 Correct 44 ms 3076 KB Output is correct
6 Correct 0 ms 344 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 463 ms 16232 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 1544 ms 51000 KB Output is correct
13 Correct 45 ms 3156 KB Output is correct
14 Correct 45 ms 3152 KB Output is correct
15 Execution timed out 2076 ms 131928 KB Time limit exceeded
16 Execution timed out 2047 ms 169376 KB Time limit exceeded
17 Execution timed out 2052 ms 97092 KB Time limit exceeded
18 Correct 24 ms 1880 KB Output is correct

Subtask #2
21.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1880 KB Output is correct
2 Execution timed out 2103 ms 228552 KB Time limit exceeded
3 Execution timed out 2093 ms 490244 KB Time limit exceeded
4 Execution timed out 2078 ms 114812 KB Time limit exceeded
5 Runtime error 1250 ms 1048576 KB Execution killed with signal 9
6 Execution timed out 2083 ms 145332 KB Time limit exceeded
7 Correct 4 ms 1624 KB Output is correct
8 Correct 5 ms 1884 KB Output is correct
9 Execution timed out 2099 ms 149884 KB Time limit exceeded
10 Correct 3 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 4 ms 3164 KB Output is correct
13 Execution timed out 2106 ms 228260 KB Time limit exceeded
14 Execution timed out 2037 ms 279964 KB Time limit exceeded
15 Correct 105 ms 40128 KB Output is correct
16 Execution timed out 2087 ms 187208 KB Time limit exceeded
17 Execution timed out 2071 ms 246748 KB Time limit exceeded
18 Correct 464 ms 156016 KB Output is correct
19 Execution timed out 2073 ms 114552 KB Time limit exceeded
20 Execution timed out 2055 ms 240192 KB Time limit exceeded
21 Execution timed out 2091 ms 347664 KB Time limit exceeded
22 Runtime error 1296 ms 1048580 KB Execution killed with signal 9
23 Execution timed out 2058 ms 387236 KB Time limit exceeded
24 Correct 909 ms 440264 KB Output is correct
25 Execution timed out 2059 ms 641580 KB Time limit exceeded
26 Correct 1882 ms 160632 KB Output is correct
27 Execution timed out 2023 ms 103808 KB Time limit exceeded
28 Execution timed out 2037 ms 134008 KB Time limit exceeded
29 Execution timed out 2049 ms 105860 KB Time limit exceeded
30 Execution timed out 2061 ms 106000 KB Time limit exceeded
31 Execution timed out 2081 ms 431944 KB Time limit exceeded
32 Execution timed out 2067 ms 116408 KB Time limit exceeded