oj.uz

Submission #469788

# Submission time Handle Problem Language Result Execution time Memory
469788 2021-09-01T18:58:35 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
31.7708 / 100
 907 ms 80884 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];

    queue<pii> q;
    int mx = 1;
    q.emplace(0, 0), dist[0][0] = 1;
    while (!q.empty()) {
        pii p = q.front();
        int i = p.ff, j = p.ss;
        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] != '.' and dist[x][y] == 0) {
                int l = (a[x][y] != a[i][j]);
                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 8 ms 3532 KB Output isn't correct
2 Correct 1 ms 460 KB Output is correct
3 Incorrect 1 ms 588 KB Output isn't correct
4 Incorrect 6 ms 3148 KB Output isn't correct
5 Incorrect 3 ms 1868 KB Output isn't correct
6 Correct 1 ms 460 KB Output is correct
7 Incorrect 1 ms 588 KB Output isn't correct
8 Incorrect 1 ms 716 KB Output isn't correct
9 Incorrect 1 ms 844 KB Output isn't correct
10 Incorrect 2 ms 1612 KB Output isn't correct
11 Incorrect 2 ms 1356 KB Output isn't correct
12 Incorrect 4 ms 1996 KB Output isn't correct
13 Incorrect 2 ms 1868 KB Output isn't correct
14 Incorrect 2 ms 1868 KB Output isn't correct
15 Incorrect 7 ms 3452 KB Output isn't correct
16 Incorrect 9 ms 3508 KB Output isn't correct
17 Incorrect 7 ms 3404 KB Output isn't correct
18 Incorrect 6 ms 3148 KB Output isn't correct

Subtask #2
28.4375 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15956 KB Output is correct
2 Incorrect 28 ms 10372 KB Output isn't correct
3 Incorrect 127 ms 59708 KB Output isn't correct
4 Incorrect 62 ms 25796 KB Output isn't correct
5 Correct 118 ms 42624 KB Output is correct
6 Incorrect 907 ms 80884 KB Output isn't correct
7 Correct 11 ms 16588 KB Output is correct
8 Correct 10 ms 15948 KB Output is correct
9 Incorrect 1 ms 716 KB Output isn't correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 10 ms 16276 KB Output is correct
12 Correct 1 ms 1100 KB Output is correct
13 Incorrect 28 ms 10444 KB Output isn't correct
14 Incorrect 17 ms 6956 KB Output isn't correct
15 Correct 17 ms 9336 KB Output is correct
16 Incorrect 14 ms 4340 KB Output isn't correct
17 Incorrect 70 ms 21164 KB Output isn't correct
18 Correct 69 ms 28292 KB Output is correct
19 Incorrect 56 ms 25648 KB Output isn't correct
20 Incorrect 35 ms 19208 KB Output isn't correct
21 Incorrect 79 ms 41352 KB Output isn't correct
22 Correct 117 ms 42632 KB Output is correct
23 Incorrect 161 ms 34644 KB Output isn't correct
24 Correct 89 ms 38724 KB Output is correct
25 Correct 376 ms 80788 KB Output is correct
26 Correct 686 ms 68728 KB Output is correct
27 Incorrect 900 ms 80880 KB Output isn't correct
28 Incorrect 890 ms 80840 KB Output isn't correct
29 Incorrect 901 ms 80732 KB Output isn't correct
30 Incorrect 879 ms 79104 KB Output isn't correct
31 Incorrect 564 ms 61708 KB Output isn't correct
32 Incorrect 743 ms 80760 KB Output isn't correct