oj.uz

Submission #469792

# Submission time Handle Problem Language Result Execution time Memory
469792 2021-09-01T19:04:07 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 617 ms 118820 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ff                  first
#define ss                  second
#define pb                  push_back
#define eb                  emplace_back
#define mp                  make_pair
#define lb                  lower_bound
#define ub                  upper_bound
#define setbits(x)          __builtin_popcountll(x)
#define zrobits(x)          __builtin_ctzll(x)
#define sz(v)               (int)v.size()
#define ps(y)               cout << fixed << setprecision(y)
#define ms(arr, v)          memset(arr, v, sizeof(arr))
#define all(v)              v.begin(), v.end()
#define rall(v)             v.rbegin(), v.rend()
#define trav(x, v)          for(auto &x: v)
#define w(t)                int t; cin >> t; while(t--)
#define rep(i, a, b)        for(int i = a; i <= b; i++)
#define rrep(i, a, b)       for(int i = a; i >= b; i--)
#define rep0(i, n)          rep(i, 0, n - 1)
#define rrep0(i, n)         rrep(i, n - 1, 0)
#define rep1(i, n)          rep(i, 1, n)
#define rrep1(i, n)         rrep(i, n, 1)
#define inp(arr, n)         rep0(i, n) cin >> arr[i];

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef map<ll, ll> mii;
typedef map<char, ll> mci;
typedef priority_queue<ll> pq_mx;
typedef priority_queue<ll, vi, greater<>> pq_mn;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> pbds;
/*
 * find_by_order(i) -> returns an iterator to the element at ith position (0 based)
 * order_of_key(i)  -> returns the position of element i (0 based)
 */

const int N = 4e3 + 5;
const int mod = 1e9 + 7;
//const int mod = 998244353;
const ll inf = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void fio() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
}

int n, m, dist[N][N];
string a[N];

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

bool valid(int x, int y) {
    return x >= 0 and y >= 0 and x < n and y < m;
}

int main() {
    fio();

    cin >> n >> m;
    rep0(x, n) cin >> a[x];

    deque<pii> q;
    int mx = 1;
    q.eb(0, 0), dist[0][0] = 1;
    while (!q.empty()) {
        auto[i, j] = q.front();
        q.pop_front(), mx = max(mx, dist[i][j]);
        rep0(d, 4) {
            int x = i + dx[d], y = j + dy[d];
            if (valid(x, y) and a[x][y] != '.' and dist[x][y] == 0) {
                int l = (a[x][y] != a[i][j]);
                if (l) q.eb(x, y);
                else q.emplace_front(x, y);
                dist[x][y] = l + dist[i][j];
            }
        }
    }
    cout << mx;


    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 3660 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 7 ms 3404 KB Output is correct
5 Correct 3 ms 1868 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 2 ms 1592 KB Output is correct
11 Correct 2 ms 1484 KB Output is correct
12 Correct 5 ms 1996 KB Output is correct
13 Correct 3 ms 1868 KB Output is correct
14 Correct 3 ms 1868 KB Output is correct
15 Correct 12 ms 3404 KB Output is correct
16 Correct 15 ms 3640 KB Output is correct
17 Correct 8 ms 3488 KB Output is correct
18 Correct 7 ms 3404 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15948 KB Output is correct
2 Correct 36 ms 10436 KB Output is correct
3 Correct 206 ms 59712 KB Output is correct
4 Correct 65 ms 25656 KB Output is correct
5 Correct 129 ms 42640 KB Output is correct
6 Correct 617 ms 93988 KB Output is correct
7 Correct 11 ms 16580 KB Output is correct
8 Correct 11 ms 15948 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 1 ms 1100 KB Output is correct
13 Correct 38 ms 10464 KB Output is correct
14 Correct 28 ms 7036 KB Output is correct
15 Correct 19 ms 9388 KB Output is correct
16 Correct 18 ms 4336 KB Output is correct
17 Correct 95 ms 21224 KB Output is correct
18 Correct 77 ms 28224 KB Output is correct
19 Correct 60 ms 25668 KB Output is correct
20 Correct 49 ms 19220 KB Output is correct
21 Correct 113 ms 41468 KB Output is correct
22 Correct 135 ms 42580 KB Output is correct
23 Correct 191 ms 34628 KB Output is correct
24 Correct 112 ms 38548 KB Output is correct
25 Correct 416 ms 80792 KB Output is correct
26 Correct 352 ms 118820 KB Output is correct
27 Correct 458 ms 98320 KB Output is correct
28 Correct 586 ms 93848 KB Output is correct
29 Correct 583 ms 94192 KB Output is correct
30 Correct 527 ms 93800 KB Output is correct
31 Correct 478 ms 62124 KB Output is correct
32 Correct 407 ms 95476 KB Output is correct