oj.uz

Submission #469773

# Submission time Handle Problem Language Result Execution time Memory
469773 2021-09-01T18:21:38 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
78.125 / 100
 2000 ms 79300 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] > l + dist[i][j]) {
                    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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 5256 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 25 ms 4812 KB Output is correct
5 Correct 12 ms 2892 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 6 ms 2508 KB Output is correct
11 Correct 5 ms 2072 KB Output is correct
12 Correct 35 ms 2996 KB Output is correct
13 Correct 12 ms 2960 KB Output is correct
14 Correct 14 ms 2964 KB Output is correct
15 Correct 75 ms 5280 KB Output is correct
16 Correct 157 ms 5312 KB Output is correct
17 Correct 103 ms 5088 KB Output is correct
18 Correct 22 ms 4804 KB Output is correct

Subtask #2
48.125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 30748 KB Output is correct
2 Correct 387 ms 16504 KB Output is correct
3 Execution timed out 2081 ms 78876 KB Time limit exceeded
4 Correct 1722 ms 30088 KB Output is correct
5 Correct 250 ms 59076 KB Output is correct
6 Execution timed out 2093 ms 79236 KB Time limit exceeded
7 Correct 15 ms 32204 KB Output is correct
8 Correct 14 ms 30752 KB Output is correct
9 Correct 14 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 15 ms 31616 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 397 ms 16460 KB Output is correct
14 Correct 194 ms 11124 KB Output is correct
15 Correct 35 ms 12140 KB Output is correct
16 Correct 353 ms 6048 KB Output is correct
17 Correct 1459 ms 32324 KB Output is correct
18 Correct 137 ms 31824 KB Output is correct
19 Correct 1705 ms 30324 KB Output is correct
20 Execution timed out 2078 ms 27952 KB Time limit exceeded
21 Execution timed out 2087 ms 61224 KB Time limit exceeded
22 Correct 250 ms 59092 KB Output is correct
23 Execution timed out 2092 ms 49632 KB Time limit exceeded
24 Correct 226 ms 60580 KB Output is correct
25 Correct 609 ms 78692 KB Output is correct
26 Correct 828 ms 68916 KB Output is correct
27 Correct 1146 ms 78768 KB Output is correct
28 Execution timed out 2081 ms 79236 KB Time limit exceeded
29 Execution timed out 2085 ms 79300 KB Time limit exceeded
30 Execution timed out 2083 ms 77552 KB Time limit exceeded
31 Execution timed out 2088 ms 64020 KB Time limit exceeded
32 Execution timed out 2090 ms 79124 KB Time limit exceeded