oj.uz

Submission #1096700

# Submission time Handle Problem Language Result Execution time Memory
1096700 2024-10-05T02:43:43 Z Captain_Katsura Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 2000 ms 177588 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(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({tmp[0],tmp[1] + dx[z],tmp[2] + dy[z]});
                    visited[tmp[1] + dx[z]][tmp[2] + dy[z]] = tmp[0];
                }
                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(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;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 66764 KB Output isn't correct
2 Incorrect 30 ms 63320 KB Output isn't correct
3 Incorrect 33 ms 63572 KB Output isn't correct
4 Incorrect 45 ms 66124 KB Output isn't correct
5 Incorrect 29 ms 64340 KB Output isn't correct
6 Incorrect 32 ms 63324 KB Output isn't correct
7 Incorrect 26 ms 63592 KB Output isn't correct
8 Incorrect 29 ms 63576 KB Output isn't correct
9 Incorrect 28 ms 63580 KB Output isn't correct
10 Incorrect 37 ms 64376 KB Output isn't correct
11 Incorrect 32 ms 64336 KB Output isn't correct
12 Incorrect 37 ms 65052 KB Output isn't correct
13 Incorrect 29 ms 64336 KB Output isn't correct
14 Incorrect 29 ms 64340 KB Output isn't correct
15 Incorrect 47 ms 65608 KB Output isn't correct
16 Incorrect 63 ms 66972 KB Output isn't correct
17 Incorrect 41 ms 65616 KB Output isn't correct
18 Incorrect 46 ms 66136 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 78160 KB Output isn't correct
2 Incorrect 104 ms 68944 KB Output isn't correct
3 Incorrect 538 ms 82272 KB Output isn't correct
4 Incorrect 123 ms 71588 KB Output isn't correct
5 Incorrect 177 ms 75088 KB Output isn't correct
6 Execution timed out 2063 ms 177492 KB Time limit exceeded
7 Incorrect 35 ms 78932 KB Output isn't correct
8 Incorrect 33 ms 78172 KB Output isn't correct
9 Incorrect 35 ms 63572 KB Output isn't correct
10 Incorrect 27 ms 63312 KB Output isn't correct
11 Incorrect 35 ms 78676 KB Output isn't correct
12 Incorrect 31 ms 63824 KB Output isn't correct
13 Incorrect 123 ms 68940 KB Output isn't correct
14 Incorrect 75 ms 67300 KB Output isn't correct
15 Incorrect 49 ms 67160 KB Output isn't correct
16 Incorrect 78 ms 65208 KB Output isn't correct
17 Incorrect 251 ms 72904 KB Output isn't correct
18 Incorrect 97 ms 71084 KB Output isn't correct
19 Incorrect 124 ms 71636 KB Output isn't correct
20 Incorrect 133 ms 71112 KB Output isn't correct
21 Incorrect 306 ms 77000 KB Output isn't correct
22 Incorrect 171 ms 75092 KB Output isn't correct
23 Incorrect 428 ms 76228 KB Output isn't correct
24 Incorrect 161 ms 75584 KB Output isn't correct
25 Incorrect 339 ms 78928 KB Output isn't correct
26 Correct 1397 ms 77336 KB Output is correct
27 Execution timed out 2015 ms 128392 KB Time limit exceeded
28 Execution timed out 2041 ms 177588 KB Time limit exceeded
29 Execution timed out 2081 ms 177492 KB Time limit exceeded
30 Execution timed out 2040 ms 177152 KB Time limit exceeded
31 Incorrect 1479 ms 125320 KB Output isn't correct
32 Incorrect 1705 ms 177496 KB Output isn't correct