oj.uz

답안 #920113

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
920113 2024-02-02T04:49:06 Z thienbao1602 Tracks in the Snow (BOI13_tracks) C++17
4.375 / 100
 794 ms 88092 KB 
#include    <bits/stdc++.h>
#define SKY
#define ll long long
#define ld long double
#define MASK(x) (1LL << x)
#define sz(x) (int)x.size()
#define ii pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define set0(d) memset(d, 0, sizeof(d))
using namespace std;

const int LOG = 20;
const int base = 311;
const ll inf = 1e18;
const int block = 400;
const ll MOD = 1e9 + 7;
const int mxN = 1e6 + 66;
const int mxN2D = 4e3 + 55;
const int x[] = {0, 1, 0, -1};
const int y[] = {1, 0, -1, 0};

int H, W;
char grid[mxN2D][mxN2D];

bool safe(int x, int y)
{
    return (x >= 0 && x < H && y >= 0 && y < W && grid[x][y] != '.');
}

void solve()
{
    cin >> H >> W;
    for (int r=0; r<H; r++)
    {
        for(int c=0; c<W; c++)
        {
            cin >> grid[r][c];
        }
    }

    deque<ii> pq;
    pq.push_back(mp(0, 0));
    vector<vector<int>> depth(H, vector<int>(W, 0));
    depth[0][0] = 1;

    int ans = 0;
    while(!pq.empty())
    {
        ii cell = pq.front();
        int u = cell.fi;
        int v = cell.se;

        ans = max(ans, depth[u][v]);
        for (int i=0; i<4; i++)
        {
            int ux = u + x[i];
            int vx = v + y[i];

            if (safe(ux, vx) && !depth[ux][vx])
            {
                depth[ux][vx] = depth[u][v] + (grid[ux][vx] != grid[u][v]);
                if (grid[ux][vx] != grid[u][v])
                {
                    pq.push_front(mp(ux, vx));
                } else
                {
                    pq.push_back(mp(ux, vx));
                }
            }
        }
        pq.pop_front();
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    #ifdef SKY
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    #endif //SKY
    solve();
    return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 3672 KB Output isn't correct
2 Incorrect 0 ms 344 KB Output isn't correct
3 Incorrect 2 ms 2648 KB Output isn't correct
4 Incorrect 7 ms 3416 KB Output isn't correct
5 Incorrect 2 ms 2904 KB Output isn't correct
6 Incorrect 0 ms 348 KB Output isn't correct
7 Incorrect 1 ms 2648 KB Output isn't correct
8 Incorrect 1 ms 2648 KB Output isn't correct
9 Incorrect 1 ms 2648 KB Output isn't correct
10 Incorrect 2 ms 2908 KB Output isn't correct
11 Incorrect 3 ms 2648 KB Output isn't correct
12 Incorrect 5 ms 2904 KB Output isn't correct
13 Incorrect 2 ms 2904 KB Output isn't correct
14 Incorrect 3 ms 2904 KB Output isn't correct
15 Incorrect 7 ms 3928 KB Output isn't correct
16 Incorrect 11 ms 3672 KB Output isn't correct
17 Incorrect 6 ms 3672 KB Output isn't correct
18 Incorrect 7 ms 3416 KB Output isn't correct

Subtask #2
4.375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 15964 KB Output isn't correct
2 Incorrect 23 ms 14168 KB Output isn't correct
3 Incorrect 227 ms 87376 KB Output isn't correct
4 Incorrect 51 ms 25748 KB Output isn't correct
5 Incorrect 123 ms 53104 KB Output isn't correct
6 Incorrect 772 ms 87396 KB Output isn't correct
7 Incorrect 4 ms 16472 KB Output isn't correct
8 Incorrect 4 ms 15960 KB Output isn't correct
9 Correct 2 ms 604 KB Output is correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Incorrect 4 ms 16220 KB Output isn't correct
12 Incorrect 1 ms 2652 KB Output isn't correct
13 Incorrect 23 ms 14016 KB Output isn't correct
14 Incorrect 13 ms 8920 KB Output isn't correct
15 Incorrect 15 ms 9304 KB Output isn't correct
16 Incorrect 9 ms 5720 KB Output isn't correct
17 Incorrect 60 ms 27052 KB Output isn't correct
18 Incorrect 55 ms 26708 KB Output isn't correct
19 Incorrect 53 ms 25800 KB Output isn't correct
20 Incorrect 59 ms 24656 KB Output isn't correct
21 Incorrect 127 ms 54356 KB Output isn't correct
22 Incorrect 126 ms 52904 KB Output isn't correct
23 Incorrect 106 ms 45600 KB Output isn't correct
24 Incorrect 127 ms 53328 KB Output isn't correct
25 Incorrect 214 ms 87384 KB Output isn't correct
26 Correct 576 ms 69716 KB Output is correct
27 Incorrect 771 ms 87632 KB Output isn't correct
28 Incorrect 759 ms 88092 KB Output isn't correct
29 Incorrect 766 ms 87900 KB Output isn't correct
30 Incorrect 794 ms 77648 KB Output isn't correct
31 Incorrect 478 ms 55160 KB Output isn't correct
32 Incorrect 646 ms 79500 KB Output isn't correct