oj.uz

답안 #720754

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
720754 2023-04-09T09:37:58 Z PanosPask Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 625 ms 181952 KB 
#include <bits/stdc++.h>
#define MAXH 4000
#define MAXW 4000

using namespace std;

typedef pair<int, int> ii;

int n, h, w;
int meadow[MAXH + 2][MAXW + 2];
bool visited[MAXH + 2][MAXW + 2];
int dist[MAXH + 2][MAXW + 2];
int ans;

bool isanimal(ii a)
{
    return meadow[a.first][a.second] != 0;
}

int calcfunc(ii a, ii b)
{
    int type1 = meadow[a.first][a.second];
    int type2 = meadow[b.first][b.second];
    if ( type1 == 0 || type2 == 0)
        return 1e9;

    return !(type1 == type2); 
}

void mod_dijkstra(ii start)
{

    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            dist[i][j] = 1e9;

    deque<ii> q;
    dist[start.first][start.second] = 1;
    q.push_front(start);

    while (!q.empty()) {
        ii node = q.front(); q.pop_front();
        if (visited[node.first][node.second])
            continue;

        visited[node.first][node.second] = true;
        ans = max(ans, dist[node.first][node.second]);
        ii neigh; 
        if (node.first > 0) {
            neigh = node;
            neigh.first--;
            if (isanimal(neigh)) {

                int d = calcfunc(node, neigh);
                if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
                    dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
                    if (d == 1)
                        q.push_back(neigh);
                    else 
                        q.push_front(neigh);
                }
            }
        }
        if (node.second > 0) {
            neigh = node;
            neigh.second--;
            if (isanimal(neigh)) {

                int d = calcfunc(node, neigh);
                if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
                    dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
                    if (d == 1)
                        q.push_back(neigh);
                    else 
                        q.push_front(neigh);
                }
            }
        }
        if (node.first < h - 1) {
            neigh = node;
            neigh.first++;
            if (isanimal(neigh)) {
                

                int d = calcfunc(node, neigh);
                if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
                    dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
                    if (d == 1)
                        q.push_back(neigh);
                    else 
                        q.push_front(neigh);
                }
            }
        }
        if (node.second < w - 1) {
            neigh = node;
            neigh.second++;
            if (isanimal(neigh)) {
                int d = calcfunc(node, neigh);
                if (dist[neigh.first][neigh.second] > d + dist[node.first][node.second]) {
                    dist[neigh.first][neigh.second] = d + dist[node.first][node.second];
                    if (d == 1)
                        q.push_back(neigh);
                    else 
                        q.push_front(neigh);
                }
            }
        }
    }
}

int main(void)
{
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; i++) {
        getchar();
        for (int j = 0; j < w; j++) {
            char c = getchar();
            if (c == '.')
                meadow[i][j] = 0;
            else if (c == 'R')
                meadow[i][j] = 1;
            else 
                meadow[i][j] = 2;
        }
    }

    mod_dijkstra(make_pair(0,0));

    printf("%d\n", ans);
    return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf("%d %d", &h, &w);
      |     ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 8348 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 1 ms 820 KB Output is correct
4 Correct 9 ms 7680 KB Output is correct
5 Correct 4 ms 4436 KB Output is correct
6 Correct 1 ms 568 KB Output is correct
7 Correct 1 ms 824 KB Output is correct
8 Correct 1 ms 980 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 4 ms 3796 KB Output is correct
11 Correct 5 ms 3008 KB Output is correct
12 Correct 5 ms 4544 KB Output is correct
13 Correct 5 ms 4436 KB Output is correct
14 Correct 4 ms 4456 KB Output is correct
15 Correct 11 ms 8508 KB Output is correct
16 Correct 12 ms 8276 KB Output is correct
17 Correct 10 ms 8116 KB Output is correct
18 Correct 8 ms 7692 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 46448 KB Output is correct
2 Correct 47 ms 29008 KB Output is correct
3 Correct 256 ms 147664 KB Output is correct
4 Correct 85 ms 54912 KB Output is correct
5 Correct 180 ms 110780 KB Output is correct
6 Correct 625 ms 160692 KB Output is correct
7 Correct 24 ms 48592 KB Output is correct
8 Correct 27 ms 46348 KB Output is correct
9 Correct 2 ms 932 KB Output is correct
10 Correct 1 ms 576 KB Output is correct
11 Correct 25 ms 47572 KB Output is correct
12 Correct 2 ms 2260 KB Output is correct
13 Correct 45 ms 28912 KB Output is correct
14 Correct 27 ms 19084 KB Output is correct
15 Correct 29 ms 21000 KB Output is correct
16 Correct 21 ms 10752 KB Output is correct
17 Correct 112 ms 58760 KB Output is correct
18 Correct 96 ms 58028 KB Output is correct
19 Correct 96 ms 54444 KB Output is correct
20 Correct 76 ms 50332 KB Output is correct
21 Correct 162 ms 113152 KB Output is correct
22 Correct 170 ms 111052 KB Output is correct
23 Correct 218 ms 92100 KB Output is correct
24 Correct 159 ms 112080 KB Output is correct
25 Correct 473 ms 148660 KB Output is correct
26 Correct 381 ms 181952 KB Output is correct
27 Correct 535 ms 177236 KB Output is correct
28 Correct 621 ms 160676 KB Output is correct
29 Correct 621 ms 161508 KB Output is correct
30 Correct 557 ms 166436 KB Output is correct
31 Correct 461 ms 117176 KB Output is correct
32 Correct 455 ms 166784 KB Output is correct