Submission #943767

#	Time	Username	Problem	Language	Result	Execution time	Memory
943767		sano	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	798 ms	257080 KiB

tracks

#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <cstdlib>
#include <random>
#include <stack>
#include <fstream>
#include <iomanip>
#include <unordered_map>
#include <queue>
#include <map>
//#include <popcntintrin.h> // Include the header file for __builtin_popcount
#define ll long long
#define For(i, n) for(ll i = 0; i < n; ++i)
#define ffor(i, a, n) for(ll i = a; i < n; ++i)
#define pb push_back
#define vec vector 
#define ff first
#define ss second
#define pairs pair<ll, ll>
#define NEK 1000000000
#define mod 1000000007
using namespace std;
typedef unsigned short int sui;

vec<vec<ll>> d;
ll naj = -1;
struct tr {
    ll x, y, w;
};

void BFS(vec<vec<char>>&p) {
    deque<tr> q;
    d[0][0] = 0;
    q.push_back({ 0, 0, 0 });
    while (!q.empty()) {
        tr x = q.front();
        q.pop_front();
        for (ll j = -1; j <= 1; j += 2) {
            if ((x.x) >= 0 && (x.x) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
                if (p[x.x][x.y + j] == '.') continue;
                if (d[x.x][x.y + j] != -1) continue;
                if (p[x.x][x.y + j] != p[x.x][x.y]) {
                    q.push_back({ x.x, x.y + j, x.w + 1 });
                    d[x.x][x.y + j] = x.w + 1;
                    naj = max(naj, d[x.x][x.y + j]);
                }
                else {
                    q.push_front({ x.x, x.y + j, x.w });
                    d[x.x][x.y + j] = x.w;
                    naj = max(naj, d[x.x][x.y + j]);
                }
            }
        }
        for (ll i = -1; i <= 1; i += 2) {
            if ((x.x + i) >= 0 && (x.x + i) < p.size() && (x.y) >= 0 && (x.y) < p[0].size()) {
                if (p[x.x + i][x.y] == '.') continue;
                if (d[x.x + i][x.y] != -1) continue;
                if (p[x.x + i][x.y] != p[x.x][x.y]) {
                    q.push_back({ x.x + i, x.y, x.w + 1 });
                    d[x.x + i][x.y] = x.w + 1;
                    naj = max(naj, d[x.x + i][x.y]);
                }
                else {
                    q.push_front({ x.x + i, x.y, x.w });
                    d[x.x + i][x.y] = x.w;
                    naj = max(naj, d[x.x + i][x.y]);
                }
            }
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //ifstream cin("subrev.in");
    //ofstream cout("subrev.out");
    ll h, w;
    cin >> h >> w;
    vec<vec<char>> p(h, vec<char>(w));
    d.resize(h, vec<ll>(w, -1));
    For(i, h) {
        For(j, w) {
            cin >> p[i][j];
        }
    }
    BFS(p);
    cout << naj+1 << '\n';
    return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'void BFS(std::vector<std::vector<char> >&)':
tracks.cpp:42:37: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if ((x.x) >= 0 && (x.x) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
      |                               ~~~~~~^~~~~~~~~~
tracks.cpp:42:79: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if ((x.x) >= 0 && (x.x) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
      |                                                                     ~~~~~~~~~~^~~~~~~~~~~~~
tracks.cpp:58:45: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if ((x.x + i) >= 0 && (x.x + i) < p.size() && (x.y) >= 0 && (x.y) < p[0].size()) {
      |                                   ~~~~~~~~~~^~~~~~~~~~
tracks.cpp:58:79: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if ((x.x + i) >= 0 && (x.x + i) < p.size() && (x.y) >= 0 && (x.y) < p[0].size()) {
      |                                                                         ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70