oj.uz

Submission #500383

# Submission time Handle Problem Language Result Execution time Memory
500383 2021-12-30T19:57:48 Z joshualiu555 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 601 ms 138756 KB 
/*
  _____                                     _        _
 / ____|                                   | |      | |
| |  __ _ __ __ _ ___ ___ _   _ _ __   ___ | |_ __ _| |_ ___
| | |_ | '__/ _` / __/ __| | | | '_ \ / _ \| __/ _` | __/ _ \
| |__| | | | (_| \__ \__ \ |_| | |_) | (_) | || (_| | || (_) |
 \_____|_|  \__,_|___/___/\__, | .__/ \___/ \__\__,_|\__\___/
                           __/ | |
                          |___/|_|
*/

#pragma gcc target ("avx2")
#pragma gcc optimization ("O3")
#pragma gcc optimization ("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> using segset = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, x, n) for (int i = x; i < n; i++)
#define F0R(i, x, n) for (int i = x; i >= n; i--)
#define TRAV(it, x) for (auto it = x.begin(); it != x.end(); it++)
#define rall(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define sz size
#define pof pop_front
#define pob pop_back
#define pf push_front
#define pb push_back
#define ins insert
#define mp make_pair
#define rz resize
#define rev reverse
#define lb lower_bound
#define ub upper_bound
// fill for 1
// 0x3f3f3f3f for 1e9
#define mem(a, x) memset(a, x, sizeof(a))

using ll = long long;
const int INF = 2e5 + 5;
const int MOD = 1e9 + 7;
// DLRU
const int dx[4] = {1, 0, 0, -1};
const int dy[4] = {0, -1, 1, 0};

/*
 *
*/

//

void solve() {

}

int n, m;
char a[4001][4001];

int dist[4001][4001];
deque<pair<int, int>> q;

bool valid(int x, int y) {
    return x >= 0 && y >= 0 && x < n && y < m && a[x][y] != '.';
}

int main()
{
    std::ios_base::sync_with_stdio(false); cin.tie(0);

//    ifstream cin(".in");
//    ofstream cout(".out");

//    int t;
//    cin >> t;
//    while (t--) {
//        solve();
//    }

    FOR(i, 0, 4001) {
        FOR(j, 0, 4001) {
            dist[i][j] = 1e9;
        }
    }

    cin >> n >> m;
    FOR(i, 0, n) cin >> a[i];

    dist[0][0] = 0;
    q.pf(mp(0, 0));
    while (q.sz()) {
        int x = q.front().first, y = q.front().second;
        q.pof();
        FOR(i, 0, 4) {
            int nx = x + dx[i], ny = y + dy[i];
            if (!valid(nx, ny)) continue;
            int w = (a[x][y] == a[nx][ny]) ^ 1;
            if (dist[x][y] + w < dist[nx][ny]) {
                dist[nx][ny] = dist[x][y] + w;
                if (w == 1) q.pb(mp(nx, ny));
                else q.pf(mp(nx, ny));
            }
        }
    }
    
//    FOR(i, 0, n) {
//        FOR(j, 0, m) {
//            cerr << dist[i][j] << ' ';
//        }
//        cerr << '\n';
//    }

    int ans = 0;
    FOR(i, 0, n) {
        FOR(j, 0, m) {
            if (dist[i][j] == 1e9) continue;
            ans = max(ans, dist[i][j]);
        }
    }
    cout << ans + 1 << '\n';

    return 0;
}

/*
 *
*/

//5 8
//FFR.....
//.FRRR...
//.FFFFF..
//..RRRFFR
//.....FFF

Compilation message

tracks.cpp:12: warning: ignoring '#pragma gcc target' [-Wunknown-pragmas]
   12 | #pragma gcc target ("avx2")
      | 
tracks.cpp:13: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   13 | #pragma gcc optimization ("O3")
      | 
tracks.cpp:14: warning: ignoring '#pragma gcc optimization' [-Wunknown-pragmas]
   14 | #pragma gcc optimization ("unroll-loops")
      |

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 65180 KB Output is correct
2 Correct 28 ms 63028 KB Output is correct
3 Correct 30 ms 63080 KB Output is correct
4 Correct 34 ms 65220 KB Output is correct
5 Correct 29 ms 64068 KB Output is correct
6 Correct 27 ms 63024 KB Output is correct
7 Correct 28 ms 63068 KB Output is correct
8 Correct 28 ms 63160 KB Output is correct
9 Correct 29 ms 63256 KB Output is correct
10 Correct 28 ms 63940 KB Output is correct
11 Correct 31 ms 63788 KB Output is correct
12 Correct 35 ms 64144 KB Output is correct
13 Correct 29 ms 64132 KB Output is correct
14 Correct 30 ms 64100 KB Output is correct
15 Correct 35 ms 65180 KB Output is correct
16 Correct 36 ms 65124 KB Output is correct
17 Correct 33 ms 64964 KB Output is correct
18 Correct 34 ms 65216 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 77944 KB Output is correct
2 Correct 57 ms 69316 KB Output is correct
3 Correct 187 ms 94328 KB Output is correct
4 Correct 78 ms 73912 KB Output is correct
5 Correct 135 ms 83440 KB Output is correct
6 Correct 601 ms 108692 KB Output is correct
7 Correct 34 ms 78668 KB Output is correct
8 Correct 34 ms 77940 KB Output is correct
9 Correct 28 ms 63024 KB Output is correct
10 Correct 27 ms 62972 KB Output is correct
11 Correct 45 ms 78276 KB Output is correct
12 Correct 29 ms 63444 KB Output is correct
13 Correct 61 ms 69288 KB Output is correct
14 Correct 45 ms 67360 KB Output is correct
15 Correct 43 ms 67716 KB Output is correct
16 Correct 41 ms 65116 KB Output is correct
17 Correct 108 ms 74832 KB Output is correct
18 Correct 97 ms 74628 KB Output is correct
19 Correct 88 ms 73988 KB Output is correct
20 Correct 65 ms 73188 KB Output is correct
21 Correct 121 ms 84120 KB Output is correct
22 Correct 130 ms 83492 KB Output is correct
23 Correct 176 ms 80292 KB Output is correct
24 Correct 121 ms 83932 KB Output is correct
25 Correct 346 ms 94300 KB Output is correct
26 Correct 377 ms 138756 KB Output is correct
27 Correct 526 ms 133844 KB Output is correct
28 Correct 596 ms 108636 KB Output is correct
29 Correct 601 ms 106512 KB Output is correct
30 Correct 562 ms 113860 KB Output is correct
31 Correct 434 ms 85928 KB Output is correct
32 Correct 460 ms 116540 KB Output is correct