oj.uz

Submission #791687

# Submission time Handle Problem Language Result Execution time Memory
791687 2023-07-24T08:50:01 Z dwuy Tracks in the Snow (BOI13_tracks) C++14
41.25 / 100
 678 ms 235804 KB 
/// (⌐■_■): "who's nvpu, dwuy?"
///  dwuy : "revolym"
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;

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

int n, m;
string a[MX];
int d[MX][MX];

void nhap(){
    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> a[i];
}

void solve(){
    deque<pii> Q;
    d[1][1] = 1;
    Q.push_front({1, 1});
    int ans = 0;
    while(Q.size()){
        int x, y;
        tie(x, y) = Q.front();
        Q.pop_front();
        ans = max(ans, d[x][y]);
        for(int i=0; i<4; i++){
            int u = x + dx[i];
            int v = y + dy[i];
            if(u<0 || u>=n || v<0 || v>=m || d[u][v]!=0 || a[u][v]=='.') continue;
            if(a[u][v] == a[x][y]){
                d[u][v] = d[x][y];
                Q.push_front({u, v});
            }
            else{
                d[u][v] = d[x][y] + 1;
                Q.push_back({u, v});
            }
        }
    }
    cout << ans;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Subtask #1
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 4820 KB Output isn't correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 6 ms 4284 KB Output is correct
5 Incorrect 3 ms 2260 KB Output isn't correct
6 Incorrect 1 ms 468 KB Output isn't correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 2 ms 1748 KB Output is correct
11 Incorrect 2 ms 1748 KB Output isn't correct
12 Correct 4 ms 2516 KB Output is correct
13 Incorrect 3 ms 2260 KB Output isn't correct
14 Incorrect 2 ms 2260 KB Output isn't correct
15 Correct 9 ms 4436 KB Output is correct
16 Incorrect 13 ms 4860 KB Output isn't correct
17 Incorrect 10 ms 4564 KB Output isn't correct
18 Correct 9 ms 4356 KB Output is correct

Subtask #2
26.25 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 16216 KB Output isn't correct
2 Incorrect 42 ms 15112 KB Output isn't correct
3 Incorrect 176 ms 93408 KB Output isn't correct
4 Correct 70 ms 43084 KB Output is correct
5 Incorrect 108 ms 69176 KB Output isn't correct
6 Correct 647 ms 184692 KB Output is correct
7 Incorrect 13 ms 16852 KB Output isn't correct
8 Incorrect 9 ms 16212 KB Output isn't correct
9 Incorrect 2 ms 980 KB Output isn't correct
10 Incorrect 1 ms 596 KB Output isn't correct
11 Incorrect 9 ms 16468 KB Output isn't correct
12 Incorrect 1 ms 1236 KB Output isn't correct
13 Incorrect 40 ms 15180 KB Output isn't correct
14 Incorrect 25 ms 9932 KB Output isn't correct
15 Incorrect 19 ms 14288 KB Output isn't correct
16 Correct 16 ms 6460 KB Output is correct
17 Incorrect 90 ms 32724 KB Output isn't correct
18 Incorrect 74 ms 47792 KB Output isn't correct
19 Correct 68 ms 43156 KB Output is correct
20 Incorrect 42 ms 27260 KB Output isn't correct
21 Correct 109 ms 61156 KB Output is correct
22 Incorrect 114 ms 69292 KB Output isn't correct
23 Correct 167 ms 56060 KB Output is correct
24 Incorrect 101 ms 59368 KB Output isn't correct
25 Incorrect 383 ms 159120 KB Output isn't correct
26 Correct 650 ms 235804 KB Output is correct
27 Correct 678 ms 198488 KB Output is correct
28 Correct 620 ms 184704 KB Output is correct
29 Correct 616 ms 182668 KB Output is correct
30 Correct 600 ms 182472 KB Output is correct
31 Correct 414 ms 115300 KB Output is correct
32 Incorrect 583 ms 177416 KB Output isn't correct