oj.uz

답안 #917507

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917507 2024-01-28T10:59:56 Z garamlee500 Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 54 ms 94472 KB 
#include <iostream>
#include <deque>
#include <vector>
#include <limits>

using namespace std;
int maxY, maxX;

//bool visited[4000][4000] = {false};
int distances[4000][4000];
vector<string> grid;

pair<int, int> add(pair<int, int> a, pair<int, int> b){
    return make_pair(a.first+b.first,a.second+b.second);
}
bool valid(pair<int, int> a){
    if (a.first<0||a.first>=maxX||a.second<0||a.second>=maxY){
        return false;
    }

    return grid[a.second][a.first]!='.';

}


int getEdge(pair<int, int> a, pair<int, int> b){
    return grid[a.second][a.first] == grid[b.second][b.first] ? 0 : 1;

}


string s;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> maxY >> maxX;
    for (int i = 0; i < maxY; i++){
        cin >> s;
        grid.push_back(s);
        for (int j = 0; j < maxX; j++){
            distances[i][j] = numeric_limits<int>::max()/2;
        }
    }

    //visited[0][0] = false;
    deque<pair<int, int>> currents;
    int best = 0;
    distances[0][0] = 0;
    currents.emplace_back(0, 0);

    while (currents.size()>0){
        pair<int, int> current = currents.front();
        currents.pop_front();
        best = max(distances[current.second][current.first], best);
        pair<int, int> nextOne;


        nextOne = add(current, make_pair(1,0));
        if (valid(nextOne)){
            int newDistance = distances[current.second][current.first] + getEdge(current, nextOne);
            if (newDistance < distances[nextOne.second][nextOne.first]){
                distances[nextOne.second][nextOne.first] = newDistance;
                if (getEdge(current, nextOne)==0){
                    currents.push_front(nextOne);
                }
                else{
                    currents.push_back(nextOne);
                }

            }
        }
    }
    cout << best + 1;


}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9048 KB Output isn't correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Incorrect 1 ms 2396 KB Output isn't correct
4 Incorrect 2 ms 9048 KB Output isn't correct
5 Incorrect 2 ms 6748 KB Output isn't correct
6 Incorrect 1 ms 2396 KB Output isn't correct
7 Incorrect 1 ms 2396 KB Output isn't correct
8 Incorrect 1 ms 2396 KB Output isn't correct
9 Incorrect 1 ms 2396 KB Output isn't correct
10 Incorrect 1 ms 4700 KB Output isn't correct
11 Incorrect 1 ms 4576 KB Output isn't correct
12 Incorrect 2 ms 6744 KB Output isn't correct
13 Incorrect 2 ms 6744 KB Output isn't correct
14 Incorrect 2 ms 6744 KB Output isn't correct
15 Incorrect 2 ms 9048 KB Output isn't correct
16 Incorrect 3 ms 9048 KB Output isn't correct
17 Incorrect 3 ms 9052 KB Output isn't correct
18 Incorrect 2 ms 8992 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 62324 KB Output isn't correct
2 Incorrect 7 ms 24156 KB Output isn't correct
3 Incorrect 46 ms 94036 KB Output isn't correct
4 Incorrect 13 ms 38744 KB Output isn't correct
5 Incorrect 27 ms 65364 KB Output isn't correct
6 Incorrect 47 ms 94152 KB Output isn't correct
7 Incorrect 10 ms 62552 KB Output isn't correct
8 Incorrect 11 ms 62296 KB Output isn't correct
9 Incorrect 1 ms 2780 KB Output isn't correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Incorrect 10 ms 62300 KB Output isn't correct
12 Incorrect 1 ms 4440 KB Output isn't correct
13 Incorrect 7 ms 24152 KB Output isn't correct
14 Incorrect 4 ms 16728 KB Output isn't correct
15 Incorrect 7 ms 18780 KB Output isn't correct
16 Incorrect 3 ms 7768 KB Output isn't correct
17 Incorrect 15 ms 41360 KB Output isn't correct
18 Incorrect 14 ms 41296 KB Output isn't correct
19 Incorrect 13 ms 38736 KB Output isn't correct
20 Incorrect 13 ms 35952 KB Output isn't correct
21 Incorrect 30 ms 67920 KB Output isn't correct
22 Incorrect 33 ms 65340 KB Output isn't correct
23 Incorrect 25 ms 54904 KB Output isn't correct
24 Incorrect 29 ms 67372 KB Output isn't correct
25 Incorrect 54 ms 94284 KB Output isn't correct
26 Correct 38 ms 79684 KB Output is correct
27 Incorrect 54 ms 94472 KB Output isn't correct
28 Incorrect 48 ms 94032 KB Output isn't correct
29 Incorrect 50 ms 94032 KB Output isn't correct
30 Incorrect 46 ms 92416 KB Output isn't correct
31 Incorrect 34 ms 72020 KB Output isn't correct
32 Incorrect 48 ms 94048 KB Output isn't correct