oj.uz

Submission #469776

# Submission time Handle Problem Language Result Execution time Memory
469776 2021-09-01T18:34:49 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 1128 ms 78816 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;
    int mx = 0;
    q.emplace(0, 0), dist[0][0] = 1;
    while (!q.empty()) {
        auto[i, j] = q.front();
        q.pop(), 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] != '.') {
                int l = a[x][y] != a[i][j];
                if (dist[x][y] == 0) {
                    dist[x][y] = l + dist[i][j];
                    q.emplace(x, y);
                }
            }
        }
    }
    cout << mx;


    return 0;
}

Subtask #1
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5068 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 9 ms 4792 KB Output isn't correct
5 Incorrect 4 ms 2764 KB Output isn't correct
6 Correct 1 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 2380 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 4 ms 2764 KB Output isn't correct
14 Incorrect 4 ms 2764 KB Output isn't correct
15 Incorrect 12 ms 4940 KB Output isn't correct
16 Incorrect 17 ms 5060 KB Output isn't correct
17 Incorrect 11 ms 4956 KB Output isn't correct
18 Incorrect 9 ms 4812 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30740 KB Output is correct
2 Incorrect 50 ms 13548 KB Output isn't correct
3 Incorrect 348 ms 57684 KB Output isn't correct
4 Incorrect 114 ms 29004 KB Output isn't correct
5 Correct 233 ms 44488 KB Output is correct
6 Incorrect 1055 ms 78672 KB Output isn't correct
7 Correct 17 ms 32204 KB Output is correct
8 Correct 17 ms 30784 KB Output is correct
9 Incorrect 2 ms 588 KB Output isn't correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 16 ms 31544 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Incorrect 50 ms 13508 KB Output isn't correct
14 Incorrect 30 ms 9396 KB Output isn't correct
15 Correct 40 ms 12100 KB Output is correct
16 Incorrect 22 ms 5092 KB Output isn't correct
17 Incorrect 136 ms 24728 KB Output isn't correct
18 Correct 139 ms 31668 KB Output is correct
19 Incorrect 110 ms 29052 KB Output isn't correct
20 Incorrect 82 ms 22256 KB Output isn't correct
21 Incorrect 209 ms 43352 KB Output isn't correct
22 Correct 243 ms 44612 KB Output is correct
23 Incorrect 262 ms 36220 KB Output isn't correct
24 Correct 211 ms 40848 KB Output is correct
25 Correct 598 ms 78656 KB Output is correct
26 Correct 872 ms 68932 KB Output is correct
27 Incorrect 1124 ms 78684 KB Output isn't correct
28 Incorrect 1077 ms 78788 KB Output isn't correct
29 Incorrect 1128 ms 78756 KB Output isn't correct
30 Incorrect 1045 ms 77120 KB Output isn't correct
31 Incorrect 690 ms 63008 KB Output isn't correct
32 Incorrect 947 ms 78816 KB Output isn't correct