oj.uz

답안 #484930

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484930 2021-11-05T18:15:33 Z Olympia Tracks in the Snow (BOI13_tracks) C++17
82.5 / 100
 2000 ms 45308 KB 
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <algorithm>
#include <iomanip>

using namespace std;
vector<vector<bool>> hasVisited;
vector<string> grid;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    priority_queue<pair<int,pair<int,int>>> q;
    grid.resize(n), hasVisited.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        hasVisited[i].resize(m);
        for (int j = 0; j < m; j++) {
            hasVisited[i][j] = false;
        }
    }
    q.push({0, {0, 0}});
    int myMax = 0;
    while (!q.empty()) {
        pair<int,int> loc = q.top().second;
        int dist = -q.top().first;
        //cout << dist << " " << loc.first << " " << loc.second << endl;
        myMax = max(myMax, dist);
        q.pop();
        if (hasVisited[loc.first][loc.second]) {
            continue;
        }
        hasVisited[loc.first][loc.second] = true;
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {
                if (abs(dx) + abs(dy) == 1 && dx + loc.first >= 0 && dy + loc.second >= 0 && dx + loc.first < n && dy + loc.second < m
                && grid[loc.first + dx][loc.second + dy] != '.') {
                    int new_dist = -dist - (grid[dx + loc.first][dy + loc.second] != grid[loc.first][loc.second]);
                    q.push(make_pair(new_dist, make_pair(loc.first + dx, loc.second + dy)));
                }
            }
        }
    }
    cout << myMax;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 1164 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 91 ms 1380 KB Output is correct
5 Correct 8 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 11 ms 448 KB Output is correct
11 Correct 23 ms 588 KB Output is correct
12 Correct 55 ms 740 KB Output is correct
13 Correct 8 ms 332 KB Output is correct
14 Correct 8 ms 456 KB Output is correct
15 Correct 108 ms 844 KB Output is correct
16 Correct 160 ms 1164 KB Output is correct
17 Correct 54 ms 772 KB Output is correct
18 Correct 91 ms 1400 KB Output is correct

Subtask #2
52.5 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 316 ms 2380 KB Output is correct
3 Correct 928 ms 20676 KB Output is correct
4 Correct 210 ms 5068 KB Output is correct
5 Correct 254 ms 11640 KB Output is correct
6 Execution timed out 2085 ms 45216 KB Time limit exceeded
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 14 ms 576 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 318 ms 2500 KB Output is correct
14 Correct 180 ms 1612 KB Output is correct
15 Correct 22 ms 1612 KB Output is correct
16 Correct 177 ms 1256 KB Output is correct
17 Correct 805 ms 5580 KB Output is correct
18 Correct 90 ms 5196 KB Output is correct
19 Correct 210 ms 5068 KB Output is correct
20 Correct 235 ms 4616 KB Output is correct
21 Correct 570 ms 12100 KB Output is correct
22 Correct 252 ms 11600 KB Output is correct
23 Correct 1613 ms 10228 KB Output is correct
24 Correct 214 ms 11680 KB Output is correct
25 Correct 435 ms 20668 KB Output is correct
26 Execution timed out 2075 ms 15896 KB Time limit exceeded
27 Execution timed out 2081 ms 22264 KB Time limit exceeded
28 Execution timed out 2085 ms 45308 KB Time limit exceeded
29 Execution timed out 2089 ms 45184 KB Time limit exceeded
30 Execution timed out 2033 ms 44956 KB Time limit exceeded
31 Execution timed out 2082 ms 16172 KB Time limit exceeded
32 Execution timed out 2083 ms 22208 KB Time limit exceeded