oj.uz

답안 #1096699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1096699 2024-10-05T02:42:30 Z Captain_Katsura Tracks in the Snow (BOI13_tracks) C++17
2.1875 / 100
 2000 ms 91476 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;
    memset(visited , 0, sizeof(visited));
    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:152:9: warning: unused variable 'cnt' [-Wunused-variable]
  152 |     int cnt = 0;
      |         ^~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 66 ms 65384 KB Output isn't correct
2 Incorrect 29 ms 63324 KB Output isn't correct
3 Incorrect 28 ms 63580 KB Output isn't correct
4 Incorrect 47 ms 65628 KB Output isn't correct
5 Incorrect 33 ms 64340 KB Output isn't correct
6 Incorrect 29 ms 63312 KB Output isn't correct
7 Incorrect 31 ms 63412 KB Output isn't correct
8 Incorrect 33 ms 63580 KB Output isn't correct
9 Incorrect 27 ms 63572 KB Output isn't correct
10 Incorrect 37 ms 64344 KB Output isn't correct
11 Incorrect 39 ms 64200 KB Output isn't correct
12 Incorrect 38 ms 64340 KB Output isn't correct
13 Incorrect 30 ms 64348 KB Output isn't correct
14 Incorrect 30 ms 64428 KB Output isn't correct
15 Incorrect 52 ms 65324 KB Output isn't correct
16 Incorrect 61 ms 65364 KB Output isn't correct
17 Incorrect 43 ms 65104 KB Output isn't correct
18 Incorrect 49 ms 65552 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 78300 KB Output isn't correct
2 Incorrect 120 ms 68624 KB Output isn't correct
3 Incorrect 638 ms 85156 KB Output isn't correct
4 Incorrect 124 ms 70716 KB Output isn't correct
5 Incorrect 171 ms 75088 KB Output isn't correct
6 Execution timed out 2029 ms 91312 KB Time limit exceeded
7 Incorrect 35 ms 78928 KB Output isn't correct
8 Incorrect 35 ms 78160 KB Output isn't correct
9 Incorrect 31 ms 63320 KB Output isn't correct
10 Incorrect 29 ms 63316 KB Output isn't correct
11 Incorrect 32 ms 78788 KB Output isn't correct
12 Incorrect 27 ms 63824 KB Output isn't correct
13 Incorrect 120 ms 68580 KB Output isn't correct
14 Incorrect 78 ms 67088 KB Output isn't correct
15 Incorrect 43 ms 67164 KB Output isn't correct
16 Incorrect 76 ms 65104 KB Output isn't correct
17 Incorrect 254 ms 71720 KB Output isn't correct
18 Incorrect 95 ms 70992 KB Output isn't correct
19 Incorrect 136 ms 70736 KB Output isn't correct
20 Incorrect 160 ms 71880 KB Output isn't correct
21 Incorrect 357 ms 78532 KB Output isn't correct
22 Incorrect 170 ms 75116 KB Output isn't correct
23 Incorrect 535 ms 74156 KB Output isn't correct
24 Incorrect 168 ms 75376 KB Output isn't correct
25 Incorrect 390 ms 78928 KB Output isn't correct
26 Correct 1424 ms 77292 KB Output is correct
27 Execution timed out 2057 ms 79952 KB Time limit exceeded
28 Execution timed out 2068 ms 91476 KB Time limit exceeded
29 Execution timed out 2019 ms 91312 KB Time limit exceeded
30 Execution timed out 2058 ms 84820 KB Time limit exceeded
31 Incorrect 1697 ms 76364 KB Output isn't correct
32 Incorrect 1723 ms 80640 KB Output isn't correct