oj.uz

Submission #1096702

# Submission time Handle Problem Language Result Execution time Memory
1096702 2024-10-05T02:46:01 Z Captain_Katsura Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 276208 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];
int visited[4010][4010];
int res = 0;
void bfs()
{
    visited[0][0] = 1;
    priority_queue<array<int,3>>pq;
    pq.push({1,0,0});
    while (!pq.empty())
    {
        array<int,3>tmp = pq.top();
        char c = G[tmp[1]][tmp[2]];
        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({tmp[0],tmp[1] + dx[z],tmp[2] + dy[z]});
                }
                else{
                    pq.push({tmp[0] + 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;
    memset(visited , 0, sizeof(visited));
    for(int i = 0; i < rows; ++i)
    {
        for(int j = 0; j < cols; ++j)
        cin >> G[i][j];
    }
    bfs();
    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;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2071 ms 163820 KB Time limit exceeded
2 Execution timed out 2068 ms 161972 KB Time limit exceeded
3 Execution timed out 2077 ms 162100 KB Time limit exceeded
4 Execution timed out 2081 ms 262252 KB Time limit exceeded
5 Execution timed out 2047 ms 64336 KB Time limit exceeded
6 Execution timed out 2040 ms 161872 KB Time limit exceeded
7 Execution timed out 2077 ms 162076 KB Time limit exceeded
8 Execution timed out 2059 ms 260644 KB Time limit exceeded
9 Execution timed out 2017 ms 162200 KB Time limit exceeded
10 Execution timed out 2074 ms 64112 KB Time limit exceeded
11 Execution timed out 2057 ms 261308 KB Time limit exceeded
12 Execution timed out 2044 ms 261612 KB Time limit exceeded
13 Execution timed out 2074 ms 64384 KB Time limit exceeded
14 Execution timed out 2029 ms 64344 KB Time limit exceeded
15 Execution timed out 2055 ms 65112 KB Time limit exceeded
16 Execution timed out 2077 ms 163912 KB Time limit exceeded
17 Execution timed out 2086 ms 65108 KB Time limit exceeded
18 Execution timed out 2083 ms 262380 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 176980 KB Time limit exceeded
2 Execution timed out 2035 ms 68180 KB Time limit exceeded
3 Execution timed out 2055 ms 276200 KB Time limit exceeded
4 Execution timed out 2055 ms 70744 KB Time limit exceeded
5 Execution timed out 2070 ms 173708 KB Time limit exceeded
6 Execution timed out 2065 ms 276204 KB Time limit exceeded
7 Execution timed out 2057 ms 177492 KB Time limit exceeded
8 Execution timed out 2054 ms 176928 KB Time limit exceeded
9 Execution timed out 2033 ms 260332 KB Time limit exceeded
10 Execution timed out 2016 ms 161876 KB Time limit exceeded
11 Execution timed out 2013 ms 177192 KB Time limit exceeded
12 Execution timed out 2074 ms 162408 KB Time limit exceeded
13 Execution timed out 2073 ms 68156 KB Time limit exceeded
14 Execution timed out 2031 ms 264072 KB Time limit exceeded
15 Execution timed out 2083 ms 67404 KB Time limit exceeded
16 Execution timed out 2081 ms 163448 KB Time limit exceeded
17 Execution timed out 2051 ms 169920 KB Time limit exceeded
18 Execution timed out 2080 ms 169788 KB Time limit exceeded
19 Execution timed out 2055 ms 70620 KB Time limit exceeded
20 Execution timed out 2055 ms 168820 KB Time limit exceeded
21 Execution timed out 2039 ms 174068 KB Time limit exceeded
22 Execution timed out 2029 ms 173640 KB Time limit exceeded
23 Execution timed out 2074 ms 270320 KB Time limit exceeded
24 Execution timed out 2019 ms 75600 KB Time limit exceeded
25 Execution timed out 2017 ms 177660 KB Time limit exceeded
26 Execution timed out 2037 ms 274160 KB Time limit exceeded
27 Execution timed out 2083 ms 275952 KB Time limit exceeded
28 Execution timed out 2073 ms 276100 KB Time limit exceeded
29 Execution timed out 2031 ms 276208 KB Time limit exceeded
30 Execution timed out 2029 ms 177232 KB Time limit exceeded
31 Execution timed out 2031 ms 273008 KB Time limit exceeded
32 Execution timed out 2045 ms 79440 KB Time limit exceeded