oj.uz

Submission #469775

# Submission time Handle Problem Language Result Execution time Memory
469775 2021-09-01T18:30:25 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 1057 ms 78868 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];
char a[N][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) inp(a[x], m)

    queue<pii> q;
    rep0(x, n) {
        rep0(y, m) dist[x][y] = 1e9;
    }
    q.emplace(0, 0), dist[0][0] = 0;
    while (!q.empty()) {
        auto[i, j] = q.front();
        q.pop();
        rep0(d, 4) {
            int x = i + dx[d], y = j + dy[d];
            if (valid(x, y) and a[x][y] != '.') {
                int l = 0;
                if (a[x][y] != a[i][j]) l = 1;
                if (dist[x][y] == 1e9) {
                    dist[x][y] = l + dist[i][j];
                    q.emplace(x, y);
                }
            }
        }
    }
    int mx = 0;
    rep0(x, n) {
        rep0(y, m) {
            if (dist[x][y] != 1e9) mx = max(mx, dist[x][y]);
        }
    }
    cout << 1 + mx;


    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 5080 KB Output isn't correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 716 KB Output isn't correct
4 Incorrect 8 ms 4812 KB Output isn't correct
5 Incorrect 4 ms 2892 KB Output isn't correct
6 Correct 0 ms 460 KB Output is correct
7 Incorrect 1 ms 716 KB Output isn't correct
8 Incorrect 1 ms 716 KB Output isn't correct
9 Incorrect 1 ms 1100 KB Output isn't correct
10 Incorrect 4 ms 2508 KB Output isn't correct
11 Incorrect 3 ms 1996 KB Output isn't correct
12 Incorrect 5 ms 2892 KB Output isn't correct
13 Incorrect 5 ms 2956 KB Output isn't correct
14 Incorrect 4 ms 2892 KB Output isn't correct
15 Incorrect 11 ms 5196 KB Output isn't correct
16 Incorrect 12 ms 5172 KB Output isn't correct
17 Incorrect 11 ms 5056 KB Output isn't correct
18 Incorrect 8 ms 4812 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 30756 KB Output is correct
2 Incorrect 53 ms 16332 KB Output isn't correct
3 Incorrect 361 ms 78696 KB Output isn't correct
4 Incorrect 113 ms 29892 KB Output isn't correct
5 Correct 240 ms 59088 KB Output is correct
6 Incorrect 1042 ms 78836 KB Output isn't correct
7 Correct 15 ms 32204 KB Output is correct
8 Correct 17 ms 30796 KB Output is correct
9 Incorrect 2 ms 588 KB Output isn't correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 14 ms 31616 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Incorrect 56 ms 16240 KB Output isn't correct
14 Incorrect 31 ms 10948 KB Output isn't correct
15 Correct 33 ms 12168 KB Output is correct
16 Incorrect 23 ms 6012 KB Output isn't correct
17 Incorrect 143 ms 32192 KB Output isn't correct
18 Correct 130 ms 31772 KB Output is correct
19 Incorrect 113 ms 29892 KB Output isn't correct
20 Incorrect 85 ms 27656 KB Output isn't correct
21 Incorrect 217 ms 61064 KB Output isn't correct
22 Correct 240 ms 59092 KB Output is correct
23 Incorrect 309 ms 49232 KB Output isn't correct
24 Correct 221 ms 60612 KB Output is correct
25 Correct 614 ms 78668 KB Output is correct
26 Correct 804 ms 68924 KB Output is correct
27 Incorrect 1037 ms 78836 KB Output isn't correct
28 Incorrect 1057 ms 78832 KB Output isn't correct
29 Incorrect 1050 ms 78868 KB Output isn't correct
30 Incorrect 1026 ms 77256 KB Output isn't correct
31 Incorrect 678 ms 63300 KB Output isn't correct
32 Incorrect 919 ms 78820 KB Output isn't correct