oj.uz

답안 #469772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469772 2021-09-01T18:19:13 Z CodeChamp_SS Tracks in the Snow (BOI13_tracks) C++17
75.9375 / 100
 2000 ms 95196 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<ll, ll> 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

# 결과 실행 시간 메모리 Grader output
1 Correct 188 ms 5572 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 24 ms 5028 KB Output is correct
5 Correct 14 ms 3148 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 844 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 6 ms 2636 KB Output is correct
11 Correct 5 ms 2124 KB Output is correct
12 Correct 43 ms 3136 KB Output is correct
13 Correct 13 ms 3048 KB Output is correct
14 Correct 13 ms 3052 KB Output is correct
15 Correct 78 ms 5568 KB Output is correct
16 Correct 178 ms 5564 KB Output is correct
17 Correct 114 ms 5372 KB Output is correct
18 Correct 24 ms 5012 KB Output is correct

Subtask #2
45.9375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 30924 KB Output is correct
2 Correct 434 ms 18024 KB Output is correct
3 Execution timed out 2090 ms 94404 KB Time limit exceeded
4 Execution timed out 2032 ms 33984 KB Time limit exceeded
5 Correct 274 ms 67832 KB Output is correct
6 Execution timed out 2081 ms 95196 KB Time limit exceeded
7 Correct 15 ms 32204 KB Output is correct
8 Correct 16 ms 30800 KB Output is correct
9 Correct 13 ms 588 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 17 ms 31692 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 432 ms 18120 KB Output is correct
14 Correct 219 ms 12100 KB Output is correct
15 Correct 37 ms 13064 KB Output is correct
16 Correct 404 ms 6768 KB Output is correct
17 Correct 1518 ms 36552 KB Output is correct
18 Correct 140 ms 35740 KB Output is correct
19 Correct 1856 ms 34036 KB Output is correct
20 Execution timed out 2093 ms 31232 KB Time limit exceeded
21 Execution timed out 2090 ms 70316 KB Time limit exceeded
22 Correct 268 ms 67876 KB Output is correct
23 Execution timed out 2097 ms 57532 KB Time limit exceeded
24 Correct 243 ms 69532 KB Output is correct
25 Correct 628 ms 94260 KB Output is correct
26 Correct 838 ms 80900 KB Output is correct
27 Correct 1174 ms 94532 KB Output is correct
28 Execution timed out 2101 ms 95192 KB Time limit exceeded
29 Execution timed out 2095 ms 95088 KB Time limit exceeded
30 Execution timed out 2096 ms 93320 KB Time limit exceeded
31 Execution timed out 2041 ms 74836 KB Time limit exceeded
32 Execution timed out 2091 ms 95056 KB Time limit exceeded