oj.uz

Submission #1096697

# Submission time Handle Problem Language Result Execution time Memory
1096697 2024-10-05T02:40:52 Z Captain_Katsura Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 2000 ms 100708 KB 
#include <iostream>
#include <cmath>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <tuple>
#include <numeric>
#include <map>
#include <bit>
#include <fstream>
#include <functional>
#include <array>
#include <chrono>
// #include<bits/stdc++.h>

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

using namespace std;

struct pair_hash {
    inline std::size_t operator()(const std::pair<int, int>& v) const {
        return v.first * 31 + v.second;
    }
};

struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
}

size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
}
};

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

#define rep(i, a, n) for(int i = a; i < n; ++i)
#define exists(s, e) (s.find(e) != s.end())
#define def_sort(s) (sort(s.begin(), s.end()))
#define def_reverse(s) (sort(s.rbegin(), s.rend()))
#define lsone(s) (s & -s)
#define endl '\n'

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

const long long INF = 1LL << 62;
using ll = long long;
using ull = unsigned long long;
typedef vector<int> vi;

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

int dx[] = { -1, 0, 1, 0, -1, 1, 1, -1 };
int dy[] = { 0, 1, 0, -1, 1, 1, -1, -1 };

const long long MOD = 1e9 + 7;
int rows, cols;

bool ok(int i, int j) {
    return (i >= 0 && j >= 0 && i < rows && j < cols);
}

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/

ull read_int() {
    bool minus = false;
    ull result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus = true;
    else result = ch - '0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result * 10 + (ch - '0');
    }
    if (minus)
        return -result;
    else
        return result;
}

template <typename T>
T mod(T a, T b = 1) {
    T rez = a % b;
    if (rez < 0)
        rez += b;
    return rez;
}

void add(ll& a, ll b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

/*–––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––*/
char G[4010][4010];
char curr[2] = {'F','R'};
int visited[4010][4010];
int res = 0;
void bfs(int x, int y, char c,int k)
{
    visited[x][y] = k;
    priority_queue<array<int,3>>pq;
    pq.push({k,x,y});
    while (!pq.empty())
    {
        array<int,3>tmp = pq.top();
        res = max(res, tmp[0]);
        pq.pop();
        for(int z = 0; z < 4; ++z)
        {
            if(ok(tmp[1] + dx[z], tmp[2] + dy[z]) && !visited[tmp[1] + dx[z]][tmp[2] + dy[z]] && G[tmp[1] + dx[z]][tmp[2] + dy[z]]!= '.')
            {
                if(G[tmp[1] + dx[z]][tmp[2] + dy[z]] == c){
                    pq.push({k,tmp[1] + dx[z],tmp[2] + dy[z]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = tmp[0];
                }
                else{
                    pq.push({k + 1,tmp[1] + dx[z],tmp[2] + dy[z]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = tmp[0] + 1;                
                }
            }
        }
    } 
    
}
void solve() {
    cin >> rows >> cols;
    int cnt = 0;
    for(int i = 0; i < rows; ++i)
    {
        for(int j = 0; j < cols; ++j)
        cin >> G[i][j];
    }
    bfs(0,0,G[0][0],1);
    cout << res << endl;    
}

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0);
#ifdef FIO
    // freopen("div7.in", "r", stdin);
    // freopen("div7.out", "w", stdout);
#endif
    // cout << setprecision(50);

int tc = 1;

#ifdef CF
    //cin >> tc;
#endif

while (tc--)
    solve();
cerr << "Time elapsed:" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:151:9: warning: unused variable 'cnt' [-Wunused-variable]
  151 |     int cnt = 0;
      |         ^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 5580 KB Output isn't correct
2 Incorrect 1 ms 604 KB Output isn't correct
3 Incorrect 1 ms 860 KB Output isn't correct
4 Incorrect 23 ms 5276 KB Output isn't correct
5 Incorrect 4 ms 2908 KB Output isn't correct
6 Incorrect 0 ms 604 KB Output isn't correct
7 Incorrect 1 ms 860 KB Output isn't correct
8 Incorrect 2 ms 860 KB Output isn't correct
9 Incorrect 1 ms 1116 KB Output isn't correct
10 Incorrect 5 ms 2600 KB Output isn't correct
11 Incorrect 7 ms 2140 KB Output isn't correct
12 Incorrect 13 ms 3128 KB Output isn't correct
13 Incorrect 4 ms 2904 KB Output isn't correct
14 Incorrect 4 ms 2908 KB Output isn't correct
15 Incorrect 29 ms 5456 KB Output isn't correct
16 Incorrect 35 ms 5376 KB Output isn't correct
17 Incorrect 17 ms 5208 KB Output isn't correct
18 Incorrect 23 ms 5148 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 30872 KB Output isn't correct
2 Incorrect 97 ms 15444 KB Output isn't correct
3 Incorrect 618 ms 77072 KB Output isn't correct
4 Incorrect 106 ms 32676 KB Output isn't correct
5 Incorrect 159 ms 53572 KB Output isn't correct
6 Execution timed out 2055 ms 100708 KB Time limit exceeded
7 Incorrect 14 ms 32348 KB Output isn't correct
8 Incorrect 13 ms 30812 KB Output isn't correct
9 Incorrect 4 ms 732 KB Output isn't correct
10 Incorrect 1 ms 348 KB Output isn't correct
11 Incorrect 12 ms 31692 KB Output isn't correct
12 Incorrect 1 ms 1628 KB Output isn't correct
13 Incorrect 96 ms 15436 KB Output isn't correct
14 Incorrect 55 ms 10712 KB Output isn't correct
15 Incorrect 21 ms 13136 KB Output isn't correct
16 Incorrect 49 ms 5816 KB Output isn't correct
17 Incorrect 248 ms 29316 KB Output isn't correct
18 Incorrect 83 ms 35664 KB Output isn't correct
19 Incorrect 101 ms 32848 KB Output isn't correct
20 Incorrect 147 ms 26752 KB Output isn't correct
21 Incorrect 360 ms 54716 KB Output isn't correct
22 Incorrect 161 ms 53372 KB Output isn't correct
23 Incorrect 491 ms 44236 KB Output isn't correct
24 Incorrect 158 ms 49748 KB Output isn't correct
25 Incorrect 377 ms 94288 KB Output isn't correct
26 Correct 1433 ms 81020 KB Output is correct
27 Execution timed out 2013 ms 91680 KB Time limit exceeded
28 Execution timed out 2027 ms 100700 KB Time limit exceeded
29 Execution timed out 2033 ms 95984 KB Time limit exceeded
30 Execution timed out 2020 ms 93880 KB Time limit exceeded
31 Incorrect 1801 ms 73644 KB Output isn't correct
32 Incorrect 1908 ms 95676 KB Output isn't correct