oj.uz

Submission #843185

# Submission time Handle Problem Language Result Execution time Memory
843185 2023-09-03T18:50:32 Z Youssif_Elkadi Tracks in the Snow (BOI13_tracks) C++17
97.8125 / 100
 728 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];
 
void dfs(int i, int j)
{
    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] && !vis[nx][ny]){
                
				fc[nx][ny]=1,vis[nx][ny]=1;
              dfs(nx, ny);
            	
            }
          else continue;
        }
        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);
  fc[0][0] = true;
    vis[0][0] = true;
    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

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9560 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 7 ms 10844 KB Output is correct
5 Correct 3 ms 5724 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4700 KB Output is correct
8 Correct 1 ms 4856 KB Output is correct
9 Correct 1 ms 4952 KB Output is correct
10 Correct 3 ms 5464 KB Output is correct
11 Correct 2 ms 5724 KB Output is correct
12 Correct 4 ms 5980 KB Output is correct
13 Correct 3 ms 5724 KB Output is correct
14 Correct 3 ms 5724 KB Output is correct
15 Correct 9 ms 9784 KB Output is correct
16 Correct 10 ms 9564 KB Output is correct
17 Correct 7 ms 9816 KB Output is correct
18 Correct 7 ms 10844 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 46684 KB Output is correct
2 Correct 40 ms 17872 KB Output is correct
3 Correct 241 ms 48212 KB Output is correct
4 Correct 59 ms 24888 KB Output is correct
5 Correct 164 ms 37908 KB Output is correct
6 Correct 515 ms 103400 KB Output is correct
7 Correct 14 ms 47708 KB Output is correct
8 Correct 13 ms 46684 KB Output is correct
9 Correct 2 ms 4956 KB Output is correct
10 Correct 1 ms 4956 KB Output is correct
11 Correct 14 ms 47456 KB Output is correct
12 Correct 1 ms 4956 KB Output is correct
13 Correct 43 ms 17632 KB Output is correct
14 Correct 22 ms 12888 KB Output is correct
15 Correct 18 ms 15708 KB Output is correct
16 Correct 17 ms 7048 KB Output is correct
17 Correct 91 ms 28072 KB Output is correct
18 Correct 71 ms 25556 KB Output is correct
19 Correct 58 ms 24924 KB Output is correct
20 Correct 56 ms 23776 KB Output is correct
21 Correct 140 ms 40528 KB Output is correct
22 Correct 162 ms 37908 KB Output is correct
23 Correct 167 ms 32084 KB Output is correct
24 Correct 158 ms 40660 KB Output is correct
25 Correct 309 ms 48148 KB Output is correct
26 Runtime error 728 ms 1048576 KB Execution killed with signal 9
27 Correct 630 ms 358708 KB Output is correct
28 Correct 517 ms 101548 KB Output is correct
29 Correct 509 ms 109844 KB Output is correct
30 Correct 464 ms 110152 KB Output is correct
31 Correct 327 ms 42736 KB Output is correct
32 Correct 366 ms 65472 KB Output is correct