oj.uz

Submission #446521

# Submission time Handle Problem Language Result Execution time Memory
446521 2021-07-22T10:15:34 Z KhoaHo Tracks in the Snow (BOI13_tracks) C++11
100 / 100
 628 ms 130768 KB 
///KhoaHo///
#include<bits/stdc++.h>
using namespace std;
///define-zone
#define task "test"
#define vec vector
#define priq priority_queue
#define pf push_front
#define pb push_back
#define popb pop_back
#define popf pop_front
#define SZ(a) a.begin(), a.end()
#define SZZ(a, begin, end) a + begin, a + begin + end
#define fi first
#define se second
#define BIT(n) (1 << n)


///typedef-zone
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
typedef double db;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

///code-mau
template<class val> inline val gcd(val a, val b){ return (a ? gcd(b%a, a): b);}
template<class val> inline val fmul(val a, val b, val m){ if (!b) return 0; if (!(b-1)) return a; if (b%2) return (fmul(a, b/2, m)*2+a)%m; else return (fmul(a, b/2, m)*2)%m; }
template<class val> inline bool getbit(val pos, val mask) {return ((mask >> pos)&1);}
void fastio()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
}
void init()
{
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}
const int N = 4004;
string snows[N];
int n, depth[N][N], ans = 1, m;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};
bool check(int x, int y)
{
    return ((x >= 0)&&(x < n)&&(y < m)&&(y >= 0)&&(snows[x][y] != '.'));
}
int main()
{
    fastio();
    ///init();
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> snows[i];
    deque<ii> dq;
    depth[0][0] = 1;
    dq.pb(ii(0, 0));
    while(!dq.empty())
    {
        int x = dq.front().fi;
        int y = dq.front().se;
        dq.popf();
        ans = max(ans, depth[x][y]);
        for(int i = 0; i < 4; i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if((check(xx, yy))&&(!depth[xx][yy]))
            {
                if(snows[x][y] == snows[xx][yy])
                {
                    depth[xx][yy] = depth[x][y];
                    dq.pf(ii(xx, yy));
                } else 
                {
                    depth[xx][yy] = depth[x][y] + 1;    
                    dq.pb(ii(xx, yy));
                }
            }
        }
    }
    cout << ans;
    return 0;
}

Compilation message

tracks.cpp: In function 'void init()':
tracks.cpp:39:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:40:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3788 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 7 ms 3524 KB Output is correct
5 Correct 3 ms 1948 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 576 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 3 ms 1612 KB Output is correct
11 Correct 2 ms 1488 KB Output is correct
12 Correct 5 ms 2124 KB Output is correct
13 Correct 3 ms 1996 KB Output is correct
14 Correct 3 ms 1996 KB Output is correct
15 Correct 10 ms 3660 KB Output is correct
16 Correct 12 ms 3788 KB Output is correct
17 Correct 8 ms 3664 KB Output is correct
18 Correct 9 ms 3488 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Correct 39 ms 11856 KB Output is correct
3 Correct 195 ms 75516 KB Output is correct
4 Correct 68 ms 29396 KB Output is correct
5 Correct 174 ms 51460 KB Output is correct
6 Correct 628 ms 110036 KB Output is correct
7 Correct 12 ms 16676 KB Output is correct
8 Correct 12 ms 15868 KB Output is correct
9 Correct 2 ms 716 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 11 ms 16332 KB Output is correct
12 Correct 2 ms 1096 KB Output is correct
13 Correct 40 ms 11820 KB Output is correct
14 Correct 22 ms 7924 KB Output is correct
15 Correct 20 ms 10316 KB Output is correct
16 Correct 19 ms 4940 KB Output is correct
17 Correct 108 ms 25180 KB Output is correct
18 Correct 102 ms 32096 KB Output is correct
19 Correct 67 ms 29276 KB Output is correct
20 Correct 49 ms 22596 KB Output is correct
21 Correct 128 ms 50552 KB Output is correct
22 Correct 187 ms 51488 KB Output is correct
23 Correct 198 ms 42308 KB Output is correct
24 Correct 126 ms 47508 KB Output is correct
25 Correct 449 ms 96324 KB Output is correct
26 Correct 350 ms 130768 KB Output is correct
27 Correct 474 ms 125852 KB Output is correct
28 Correct 616 ms 110012 KB Output is correct
29 Correct 605 ms 108080 KB Output is correct
30 Correct 556 ms 114380 KB Output is correct
31 Correct 484 ms 72144 KB Output is correct
32 Correct 454 ms 114860 KB Output is correct