oj.uz

Submission #1015805

# Submission time Handle Problem Language Result Execution time Memory
1015805 2024-07-06T20:26:31 Z lucascgar Tracks in the Snow (BOI13_tracks) C++17
89.0625 / 100
 2000 ms 119464 KB 
#include <bits/stdc++.h>

// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

using namespace std;

/*
two puddles of the same type are intersected by one with connection to start, then its all 2 animals only

começo no início
    - tudo q eu percorrer é 1 bicho só, todos os diferentes adjacentes a ele são do mesmo bicho só, e assim por diante

*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // overclock random

typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef pair<double, double> pdd;

const int MAXN = 4e3+12;


char g[MAXN][MAXN];

int d[MAXN][MAXN], aux[4] = {1,-1, 0, 0};

signed main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    // cout << fixed << setprecision(12);

    int n, m;
    cin >> n >> m;
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){
        cin >> g[i][j];
        d[i][j] = 1e9;
        if (g[i][j] == '.') d[i][j] = -1;
    }

    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<>> q;

    q.push({1, {1,1}});
    d[1][1] = 1;
    int ans=1;
    while (!q.empty()){
        auto u = q.top();
        q.pop();
        if (u.first != d[u.second.first][u.second.second]) continue;
        
        ans = max(ans, u.first);
        pii x = u.second;
        char t = g[x.first][x.second];

        for (int a=0,b=3;a<4;a++,b--){
            int ni = x.first+aux[a],nj=x.second+aux[b];
            if (d[ni][nj] == -1) continue;

            int nd = u.first + (t != g[ni][nj]);

            if (d[ni][nj] <= nd) continue;

            d[ni][nj] = nd;
            q.push({nd, {ni,nj}});
        }

    }

    cout << ans << "\n";

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5720 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 24 ms 5404 KB Output is correct
5 Correct 4 ms 3204 KB Output is correct
6 Correct 0 ms 604 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 860 KB Output is correct
9 Correct 2 ms 1116 KB Output is correct
10 Correct 4 ms 2652 KB Output is correct
11 Correct 5 ms 2304 KB Output is correct
12 Correct 12 ms 3164 KB Output is correct
13 Correct 4 ms 3164 KB Output is correct
14 Correct 5 ms 3040 KB Output is correct
15 Correct 25 ms 5756 KB Output is correct
16 Correct 34 ms 5720 KB Output is correct
17 Correct 18 ms 5468 KB Output is correct
18 Correct 21 ms 5424 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31068 KB Output is correct
2 Correct 95 ms 18108 KB Output is correct
3 Correct 363 ms 93304 KB Output is correct
4 Correct 113 ms 34128 KB Output is correct
5 Correct 153 ms 69308 KB Output is correct
6 Execution timed out 2027 ms 119464 KB Time limit exceeded
7 Correct 13 ms 36444 KB Output is correct
8 Correct 12 ms 33628 KB Output is correct
9 Correct 4 ms 4700 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 12 ms 34500 KB Output is correct
12 Correct 1 ms 4444 KB Output is correct
13 Correct 98 ms 19140 KB Output is correct
14 Correct 53 ms 13404 KB Output is correct
15 Correct 21 ms 14428 KB Output is correct
16 Correct 47 ms 8116 KB Output is correct
17 Correct 255 ms 37968 KB Output is correct
18 Correct 79 ms 37460 KB Output is correct
19 Correct 122 ms 36044 KB Output is correct
20 Correct 87 ms 32852 KB Output is correct
21 Correct 212 ms 71508 KB Output is correct
22 Correct 157 ms 69200 KB Output is correct
23 Correct 457 ms 58448 KB Output is correct
24 Correct 156 ms 70712 KB Output is correct
25 Correct 349 ms 94584 KB Output is correct
26 Correct 907 ms 82472 KB Output is correct
27 Execution timed out 2064 ms 97748 KB Time limit exceeded
28 Execution timed out 2076 ms 119192 KB Time limit exceeded
29 Execution timed out 2064 ms 106912 KB Time limit exceeded
30 Execution timed out 2062 ms 105024 KB Time limit exceeded
31 Correct 1599 ms 75448 KB Output is correct
32 Correct 1618 ms 96360 KB Output is correct