oj.uz

Submission #490974

# Submission time Handle Problem Language Result Execution time Memory
490974 2021-11-30T02:36:25 Z sberens Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 158116 KB 
#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template<typename K> using hset = gp_hash_table<K, null_type>;
template<typename K, typename V> using hmap = gp_hash_table<K, V>;


using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define smax(x, y) (x = max(x, y))
#define smin(x, y) (x = min(x, y))

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i, a) ROF(i,0,a)


using ll = long long;
using ld = long double;

template<typename T>
using vv = vector<vector<T>>;

using vi = vector<int>;
using ii = array<int, 2>;
using vii = vector<ii>;
using vvi = vv<int>;

using vll = vector<ll>;
using l2 = array<ll, 2>;
using vl2 = vector<l2>;
using vvll = vv<ll>;

template<typename T>
using minq = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using maxq = priority_queue<T>;

const ll M = 1000000007;
const ll infll = M * M;

vii dirs{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

vii adjc(int x, int y) {
    vii res;
    for (auto [dx, dy] : dirs) {
        res.pb({x + dx, y + dy});
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    vvi g(h, vi(w));
    F0R(r, h) {
        F0R(c, w) {
            char x;
            cin >> x;
            g[r][c] = x;
        }
    }
    int res = 0;
    int p = '.';
    deque<ii> q; // r, c
    q.push_front({0, 0});
    vvi seen(h, vi(w));
    seen[0][0] = 1;
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop_front();
        if (g[r][c] != p) res++;
        p = g[r][c];
        for (auto [nr, nc] : adjc(r, c)) {
            if (0 <= nr && nr < h && 0 <= nc && nc < w && seen[nr][nc] == 0 && g[nr][nc] != '.') {
                if (g[nr][nc] == p) q.push_front({nr, nc});
                else q.push_back({nr, nc});
                seen[nr][nc] = 1;
            }
        }
    }
    cout << res << '\n';

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2508 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 21 ms 1868 KB Output is correct
5 Correct 5 ms 988 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 5 ms 844 KB Output is correct
11 Correct 5 ms 716 KB Output is correct
12 Correct 12 ms 1100 KB Output is correct
13 Correct 4 ms 972 KB Output is correct
14 Correct 5 ms 1072 KB Output is correct
15 Correct 27 ms 2576 KB Output is correct
16 Correct 34 ms 2500 KB Output is correct
17 Correct 20 ms 2456 KB Output is correct
18 Correct 20 ms 1912 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 968 KB Output is correct
2 Correct 111 ms 14144 KB Output is correct
3 Correct 717 ms 131664 KB Output is correct
4 Correct 159 ms 33480 KB Output is correct
5 Correct 577 ms 77300 KB Output is correct
6 Execution timed out 2037 ms 145384 KB Time limit exceeded
7 Correct 3 ms 972 KB Output is correct
8 Correct 4 ms 972 KB Output is correct
9 Correct 5 ms 844 KB Output is correct
10 Correct 2 ms 612 KB Output is correct
11 Correct 3 ms 972 KB Output is correct
12 Correct 2 ms 460 KB Output is correct
13 Correct 114 ms 14124 KB Output is correct
14 Correct 63 ms 8268 KB Output is correct
15 Correct 52 ms 9112 KB Output is correct
16 Correct 59 ms 5980 KB Output is correct
17 Correct 292 ms 36164 KB Output is correct
18 Correct 199 ms 35736 KB Output is correct
19 Correct 156 ms 33468 KB Output is correct
20 Correct 172 ms 30844 KB Output is correct
21 Correct 424 ms 79880 KB Output is correct
22 Correct 622 ms 77480 KB Output is correct
23 Correct 560 ms 67520 KB Output is correct
24 Correct 474 ms 77964 KB Output is correct
25 Correct 1026 ms 131524 KB Output is correct
26 Correct 1500 ms 151584 KB Output is correct
27 Execution timed out 2084 ms 158116 KB Time limit exceeded
28 Execution timed out 2069 ms 145124 KB Time limit exceeded
29 Execution timed out 2074 ms 143040 KB Time limit exceeded
30 Execution timed out 2061 ms 145884 KB Time limit exceeded
31 Correct 1576 ms 86752 KB Output is correct
32 Correct 1715 ms 145276 KB Output is correct