oj.uz

Submission #1096703

# Submission time Handle Problem Language Result Execution time Memory
1096703 2024-10-05T02:47:06 Z Captain_Katsura Tracks in the Snow (BOI13_tracks) C++17
29.5833 / 100
 2000 ms 177612 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]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = 1;
                }
                else{
                    pq.push({tmp[0] + 1,tmp[1] + dx[z],tmp[2] + dy[z]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = 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
3.33333333333 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 66764 KB Output isn't correct
2 Correct 27 ms 63316 KB Output is correct
3 Incorrect 27 ms 63572 KB Output isn't correct
4 Incorrect 48 ms 66760 KB Output isn't correct
5 Incorrect 30 ms 64340 KB Output isn't correct
6 Correct 25 ms 63264 KB Output is correct
7 Incorrect 26 ms 63576 KB Output isn't correct
8 Incorrect 27 ms 63432 KB Output isn't correct
9 Incorrect 29 ms 63572 KB Output isn't correct
10 Incorrect 36 ms 64340 KB Output isn't correct
11 Incorrect 35 ms 64540 KB Output isn't correct
12 Incorrect 38 ms 65052 KB Output isn't correct
13 Incorrect 44 ms 64336 KB Output isn't correct
14 Incorrect 31 ms 64540 KB Output isn't correct
15 Incorrect 52 ms 65480 KB Output isn't correct
16 Incorrect 79 ms 66760 KB Output isn't correct
17 Incorrect 44 ms 65612 KB Output isn't correct
18 Incorrect 58 ms 66764 KB Output isn't correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 78160 KB Output is correct
2 Incorrect 140 ms 69192 KB Output isn't correct
3 Incorrect 550 ms 82108 KB Output isn't correct
4 Incorrect 118 ms 71500 KB Output isn't correct
5 Correct 211 ms 75088 KB Output is correct
6 Execution timed out 2043 ms 177612 KB Time limit exceeded
7 Correct 36 ms 78932 KB Output is correct
8 Correct 36 ms 78144 KB Output is correct
9 Incorrect 33 ms 63320 KB Output isn't correct
10 Correct 27 ms 63324 KB Output is correct
11 Incorrect 37 ms 78736 KB Output isn't correct
12 Correct 28 ms 63824 KB Output is correct
13 Incorrect 116 ms 68936 KB Output isn't correct
14 Incorrect 82 ms 67304 KB Output isn't correct
15 Correct 51 ms 67156 KB Output is correct
16 Incorrect 72 ms 65300 KB Output isn't correct
17 Incorrect 275 ms 72908 KB Output isn't correct
18 Correct 104 ms 70992 KB Output is correct
19 Incorrect 124 ms 71500 KB Output isn't correct
20 Incorrect 137 ms 71108 KB Output isn't correct
21 Incorrect 356 ms 77060 KB Output isn't correct
22 Correct 187 ms 75088 KB Output is correct
23 Incorrect 423 ms 76488 KB Output isn't correct
24 Correct 168 ms 75580 KB Output is correct
25 Correct 359 ms 79048 KB Output is correct
26 Correct 1406 ms 77292 KB Output is correct
27 Execution timed out 2062 ms 177560 KB Time limit exceeded
28 Execution timed out 2052 ms 177488 KB Time limit exceeded
29 Execution timed out 2060 ms 177492 KB Time limit exceeded
30 Execution timed out 2063 ms 177232 KB Time limit exceeded
31 Incorrect 1518 ms 125208 KB Output isn't correct
32 Incorrect 1698 ms 128388 KB Output isn't correct