oj.uz

Submission #469778

# Submission time Handle Problem Language Result Execution time Memory
469778 2021-09-01T18:36:09 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 1102 ms 78732 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 = 1;
    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 4812 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 2 ms 1100 KB Output isn't correct
10 Incorrect 3 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 15 ms 4948 KB Output isn't correct
16 Incorrect 13 ms 5156 KB Output isn't correct
17 Incorrect 27 ms 4932 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 17 ms 30704 KB Output is correct
2 Incorrect 51 ms 13468 KB Output isn't correct
3 Incorrect 343 ms 57696 KB Output isn't correct
4 Incorrect 111 ms 28992 KB Output isn't correct
5 Correct 235 ms 44580 KB Output is correct
6 Incorrect 1077 ms 78704 KB Output isn't correct
7 Correct 18 ms 32204 KB Output is correct
8 Correct 20 ms 30784 KB Output is correct
9 Incorrect 2 ms 588 KB Output isn't correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 17 ms 31548 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Incorrect 62 ms 13448 KB Output isn't correct
14 Incorrect 38 ms 9524 KB Output isn't correct
15 Correct 35 ms 12020 KB Output is correct
16 Incorrect 23 ms 5196 KB Output isn't correct
17 Incorrect 133 ms 24700 KB Output isn't correct
18 Correct 143 ms 31764 KB Output is correct
19 Incorrect 109 ms 29068 KB Output isn't correct
20 Incorrect 80 ms 22280 KB Output isn't correct
21 Incorrect 206 ms 43400 KB Output isn't correct
22 Correct 239 ms 44484 KB Output is correct
23 Incorrect 262 ms 36236 KB Output isn't correct
24 Correct 218 ms 40900 KB Output is correct
25 Correct 609 ms 78552 KB Output is correct
26 Correct 840 ms 68872 KB Output is correct
27 Incorrect 1092 ms 78600 KB Output isn't correct
28 Incorrect 1102 ms 78732 KB Output isn't correct
29 Incorrect 1095 ms 78624 KB Output isn't correct
30 Incorrect 1047 ms 77064 KB Output isn't correct
31 Incorrect 681 ms 63052 KB Output isn't correct
32 Incorrect 944 ms 78624 KB Output isn't correct