oj.uz

Submission #943764

# Submission time Handle Problem Language Result Execution time Memory
943764 2024-03-11T20:43:29 Z sano Tracks in the Snow (BOI13_tracks) C++17
57.7083 / 100
 695 ms 147512 KB 
#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

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.3333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1884 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Incorrect 6 ms 1488 KB Output isn't correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Incorrect 2 ms 856 KB Output isn't correct
11 Incorrect 2 ms 604 KB Output isn't correct
12 Incorrect 4 ms 1044 KB Output isn't correct
13 Correct 2 ms 976 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 8 ms 1956 KB Output is correct
16 Correct 10 ms 1996 KB Output is correct
17 Correct 7 ms 1884 KB Output is correct
18 Incorrect 6 ms 1628 KB Output isn't correct

Subtask #2
39.375 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1112 KB Output isn't correct
2 Incorrect 38 ms 9716 KB Output isn't correct
3 Incorrect 275 ms 94672 KB Output isn't correct
4 Incorrect 70 ms 22492 KB Output isn't correct
5 Correct 179 ms 53248 KB Output is correct
6 Correct 663 ms 113600 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Incorrect 2 ms 1056 KB Output isn't correct
9 Correct 2 ms 828 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Incorrect 1 ms 860 KB Output isn't correct
12 Correct 1 ms 344 KB Output is correct
13 Incorrect 37 ms 9552 KB Output isn't correct
14 Correct 21 ms 5724 KB Output is correct
15 Incorrect 18 ms 6296 KB Output isn't correct
16 Incorrect 18 ms 4188 KB Output isn't correct
17 Incorrect 101 ms 24256 KB Output isn't correct
18 Incorrect 82 ms 24080 KB Output isn't correct
19 Incorrect 68 ms 22356 KB Output isn't correct
20 Correct 59 ms 20560 KB Output is correct
21 Correct 158 ms 55376 KB Output is correct
22 Correct 163 ms 53380 KB Output is correct
23 Correct 191 ms 45940 KB Output is correct
24 Correct 156 ms 53844 KB Output is correct
25 Correct 515 ms 94676 KB Output is correct
26 Incorrect 656 ms 147512 KB Output isn't correct
27 Correct 695 ms 124424 KB Output is correct
28 Correct 668 ms 113796 KB Output is correct
29 Correct 650 ms 111832 KB Output is correct
30 Correct 634 ms 112296 KB Output is correct
31 Incorrect 409 ms 61672 KB Output isn't correct
32 Correct 677 ms 113716 KB Output is correct