oj.uz

답안 #843164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843164 2023-09-03T18:30:34 Z Youssif_Elkadi Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 676 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define F first
#define S second
const int N = 4000;
int n, m, ans = 1;
char c[N][N];
bool fc[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
vector<pair<int, int>> f, r;
bool vis[N][N];
int cnt = 0;
void dfs(int i, int j)
{
    cnt++;
    if (cnt >= n * m)
        return;
    fc[i][j] = true;
    vis[i][j] = true;
    for (int ii = 0; ii < 4; ii++)
    {
        int nx = i + dx[ii], ny = j + dy[ii];
        if (nx < 0 || ny < 0 || nx >= n || ny >= m)
            continue;
        if (c[nx][ny] == c[0][0])
        {
            if (!fc[nx][ny])
                dfs(nx, ny);
        }
        else if (!vis[nx][ny])
        {
            if (c[nx][ny] == 'F')
                f.pb({nx, ny});
            else if (c[nx][ny] == 'R')
                r.pb({nx, ny});
            vis[nx][ny] = true;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> c[i][j];
        }
    }
    dfs(0, 0);
    char cur = 'R';
    if (c[0][0] == cur)
        cur = 'F';
    while (!f.empty() || !r.empty())
    {
        if (cur == 'R')
        {
            if (!r.empty())
                ans++;
            while (!r.empty())
            {
                int x = r.back().F, y = r.back().S;
                r.pop_back();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dx[i], ny = y + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                        continue;
                    if (vis[nx][ny])
                        continue;
                    vis[nx][ny] = true;
                    if (c[nx][ny] == 'R')
                        r.pb({nx, ny});
                    else if (c[nx][ny] == 'F')
                        f.pb({nx, ny});
                }
            }
        }
        else
        {
            if (!f.empty())
            {
                ans++;
            }
            while (!f.empty())
            {
                int x = f.back().F, y = f.back().S;
                f.pop_back();
                for (int i = 0; i < 4; i++)
                {
                    int nx = x + dx[i], ny = y + dy[i];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                        continue;
                    if (vis[nx][ny])
                        continue;
                    vis[nx][ny] = true;
                    if (c[nx][ny] == 'R')
                        r.pb({nx, ny});
                    else if (c[nx][ny] == 'F')
                        f.pb({nx, ny});
                }
            }
        }
        if (cur == 'F')
            cur = 'R';
        else
            cur = 'F';
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 10076 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 7 ms 11232 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 6748 KB Output is correct
10 Correct 2 ms 5468 KB Output is correct
11 Correct 2 ms 7004 KB Output is correct
12 Correct 4 ms 7004 KB Output is correct
13 Correct 3 ms 5724 KB Output is correct
14 Correct 2 ms 5724 KB Output is correct
15 Correct 9 ms 9784 KB Output is correct
16 Correct 10 ms 10136 KB Output is correct
17 Correct 8 ms 9564 KB Output is correct
18 Correct 7 ms 11168 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 46684 KB Output is correct
2 Correct 37 ms 19036 KB Output is correct
3 Correct 228 ms 48076 KB Output is correct
4 Correct 63 ms 24916 KB Output is correct
5 Correct 158 ms 38660 KB Output is correct
6 Correct 484 ms 102352 KB Output is correct
7 Correct 10 ms 47552 KB Output is correct
8 Correct 10 ms 46712 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 5108 KB Output is correct
11 Correct 10 ms 47452 KB Output is correct
12 Correct 1 ms 6948 KB Output is correct
13 Correct 36 ms 19168 KB Output is correct
14 Correct 21 ms 12896 KB Output is correct
15 Correct 16 ms 15960 KB Output is correct
16 Correct 17 ms 7000 KB Output is correct
17 Correct 88 ms 28576 KB Output is correct
18 Correct 62 ms 26352 KB Output is correct
19 Correct 62 ms 24912 KB Output is correct
20 Correct 54 ms 25308 KB Output is correct
21 Correct 135 ms 41112 KB Output is correct
22 Correct 160 ms 38612 KB Output is correct
23 Correct 169 ms 32084 KB Output is correct
24 Correct 141 ms 41040 KB Output is correct
25 Correct 274 ms 48072 KB Output is correct
26 Runtime error 676 ms 1048576 KB Execution killed with signal 9
27 Correct 595 ms 357824 KB Output is correct
28 Correct 493 ms 104020 KB Output is correct
29 Correct 483 ms 111032 KB Output is correct
30 Correct 448 ms 111400 KB Output is correct
31 Correct 317 ms 42716 KB Output is correct
32 Correct 363 ms 65852 KB Output is correct