Submission #943764

#	Time	Username	Problem	Language	Result	Execution time	Memory
943764		sano	Tracks in the Snow (BOI13_tracks)	C++17	57.71 / 100	695 ms	147512 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<int, int>
#define NEK 1000000000000000000
#define mod 1000000007
using namespace std;
typedef unsigned short int sui;

vec<vec<int>> d;
int naj = -1;
struct tr {
    int 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();
        int i2 = 0;
        for (int j = -1; j <= 1; j += 2) {
            if ((x.x + i2) >= 0 && (x.x + i2) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
                if (p[x.x + i2][x.y + j] == '.') continue;
                if (d[x.x + i2][x.y + j] != -1) continue;
                if (p[x.x + i2][x.y + j] != p[x.x][x.y]) {
                    q.push_back({ x.x + i2, x.y + j, x.w + 1 });
                    d[x.x + i2][x.y + j] = x.w + 1;
                    naj = max(naj, d[x.x + i2][x.y + j]);
                }
                else {
                    q.push_front({ x.x + i2, x.y + j, x.w });
                    d[x.x + i2][x.y + j] = x.w + 1;
                    naj = max(naj, d[x.x + i2][x.y + j]);
                }
            }
        }
        int j = 0;
        for (int i = -1; i <= 1; i += 2) {
            if ((x.x + i) >= 0 && (x.x + i) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
                if (p[x.x + i][x.y + j] == '.') continue;
                if (d[x.x + i][x.y + j] != -1) continue;
                if (p[x.x + i][x.y + j] != p[x.x][x.y]) {
                    q.push_back({ x.x + i, x.y + j, x.w + 1 });
                    d[x.x + i][x.y + j] = x.w + 1;
                    naj = max(naj, d[x.x + i][x.y + j]);
                }
                else {
                    q.push_front({ x.x + i, x.y + j, x.w });
                    d[x.x + i][x.y + j] = x.w + 1;
                    naj = max(naj, d[x.x + i][x.y + j]);
                }
            }
        }
    }
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //ifstream cin("subrev.in");
    //ofstream cout("subrev.out");
    int h, w;
    cin >> h >> w;
    vec<vec<char>> p(h, vec<char>(w));
    d.resize(h, vec<int>(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:43:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             if ((x.x + i2) >= 0 && (x.x + i2) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
      |                                    ~~~~~~~~~~~^~~~~~~~~~
tracks.cpp:43:89: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             if ((x.x + i2) >= 0 && (x.x + i2) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
      |                                                                               ~~~~~~~~~~^~~~~~~~~~~~~
tracks.cpp:60:45: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             if ((x.x + i) >= 0 && (x.x + i) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
      |                                   ~~~~~~~~~~^~~~~~~~~~
tracks.cpp:60:87: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             if ((x.x + i) >= 0 && (x.x + i) < p.size() && (x.y + j) >= 0 && (x.y + j) < p[0].size()) {
      |                                                                             ~~~~~~~~~~^~~~~~~~~~~~~

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