oj.uz

답안 #1072599

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1072599 2024-08-23T23:02:48 Z redLotus31415 Tracks in the Snow (BOI13_tracks) C++17
45.2083 / 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, 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2066 ms 166020 KB Time limit exceeded
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 23 ms 1788 KB Output is correct
5 Correct 45 ms 3164 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 487 ms 16136 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 1573 ms 50956 KB Output is correct
13 Correct 51 ms 3164 KB Output is correct
14 Correct 48 ms 3156 KB Output is correct
15 Execution timed out 2084 ms 132456 KB Time limit exceeded
16 Execution timed out 2074 ms 162812 KB Time limit exceeded
17 Execution timed out 2058 ms 95292 KB Time limit exceeded
18 Correct 29 ms 1876 KB Output is correct

Subtask #2
21.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1880 KB Output is correct
2 Execution timed out 2093 ms 227636 KB Time limit exceeded
3 Execution timed out 2084 ms 492344 KB Time limit exceeded
4 Execution timed out 2061 ms 115308 KB Time limit exceeded
5 Runtime error 1316 ms 1048576 KB Execution killed with signal 9
6 Execution timed out 2045 ms 136460 KB Time limit exceeded
7 Correct 4 ms 1628 KB Output is correct
8 Correct 4 ms 1952 KB Output is correct
9 Execution timed out 2105 ms 143344 KB Time limit exceeded
10 Correct 3 ms 1112 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 2083 ms 228408 KB Time limit exceeded
14 Execution timed out 2078 ms 279752 KB Time limit exceeded
15 Correct 116 ms 40384 KB Output is correct
16 Execution timed out 2032 ms 187828 KB Time limit exceeded
17 Execution timed out 2069 ms 246208 KB Time limit exceeded
18 Correct 508 ms 156272 KB Output is correct
19 Execution timed out 2066 ms 114288 KB Time limit exceeded
20 Execution timed out 2037 ms 220632 KB Time limit exceeded
21 Execution timed out 2048 ms 333052 KB Time limit exceeded
22 Runtime error 1293 ms 1048576 KB Execution killed with signal 9
23 Execution timed out 2085 ms 391164 KB Time limit exceeded
24 Correct 894 ms 440260 KB Output is correct
25 Execution timed out 2087 ms 641488 KB Time limit exceeded
26 Correct 1829 ms 160500 KB Output is correct
27 Execution timed out 2073 ms 103708 KB Time limit exceeded
28 Execution timed out 2016 ms 140040 KB Time limit exceeded
29 Execution timed out 2084 ms 110464 KB Time limit exceeded
30 Execution timed out 2084 ms 105840 KB Time limit exceeded
31 Execution timed out 2105 ms 431360 KB Time limit exceeded
32 Execution timed out 2067 ms 116412 KB Time limit exceeded