oj.uz

Submission #1083778

# Submission time Handle Problem Language Result Execution time Memory
1083778 2024-09-04T06:30:19 Z altern23 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 745 ms 256852 KB 
#include <bits/stdc++.h>
#include <functional>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds; 

#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long
#define pii pair<ll,ll>
#define fi first
#define sec second
#define double long double
#define debug(x) cout << #x << " = " << x << "\n";

const ll MOD = 1e9 + 7;
const ll N = 1e6 + 5;
const ll INF = 1e18;

template <typename T>
ostream& operator << (ostream& os, vector<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";

    return os;
}

template <typename T>
ostream& operator << (ostream& os, set<T>tmp){
    os << "[";
    for(auto x : tmp) os << " " << x;
    os << " ]";

    return os;
}

ll a[N];

ostream& operator << (ostream& os, pii x){
    os << "[";
    os << " " << x.fi << " " << x.sec;
    os << " ]";

    return os;
}

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);
    int tc = 1;
    // cin >> tc;
    for(;tc--;){
        ll h,w; cin >> h >> w;

        char grid[h + 5][w + 5];
        ll dist[h + 5][w + 5];

        memset(dist, 0x3f, sizeof(dist));

        dist[1][1] = 1;
        
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++) cin >> grid[i][j];
        }

        deque<pair<ll, pii>>dq;
        dq.push_back({1, {1, 1}});

        ll di[] = {0, 0, 1, -1}, dj[] = {1, -1, 0, 0};
        for(;!dq.empty();){
            auto x = dq.front(); dq.pop_front();
            if(x.fi > dist[x.sec.fi][x.sec.sec]) continue;

            for(int i=0;i<4;i++){
                ll newi = x.sec.fi + di[i], newj = x.sec.sec + dj[i];
                if(newi < 1 || newj < 1 || newi > h || newj > w) continue;
                if(grid[newi][newj] == '.' || dist[newi][newj] <= x.fi + (grid[newi][newj] != grid[x.sec.fi][x.sec.sec])) continue;
                dist[newi][newj] = x.fi + (grid[newi][newj] != grid[x.sec.fi][x.sec.sec]);

                if(grid[newi][newj] != grid[x.sec.fi][x.sec.sec]) dq.push_back({dist[newi][newj], {newi, newj}});
                else dq.push_front({dist[newi][newj], {newi, newj}});
            }
        }

        ll mx = 1;
        for(int i=1;i<=h;i++){
            for(int j=1;j<=w;j++){
                if(grid[i][j] != '.') mx = max(mx, dist[i][j]);
            }
        }

        cout << mx << "\n";
    }
} 

/*

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2652 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 2396 KB Output is correct
5 Correct 2 ms 1116 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 4 ms 1368 KB Output is correct
13 Correct 2 ms 1116 KB Output is correct
14 Correct 2 ms 1116 KB Output is correct
15 Correct 9 ms 2652 KB Output is correct
16 Correct 10 ms 2652 KB Output is correct
17 Correct 13 ms 2396 KB Output is correct
18 Correct 8 ms 2396 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 46 ms 14168 KB Output is correct
3 Correct 351 ms 141608 KB Output is correct
4 Correct 89 ms 33644 KB Output is correct
5 Correct 198 ms 79956 KB Output is correct
6 Correct 679 ms 180736 KB Output is correct
7 Correct 1 ms 856 KB Output is correct
8 Correct 1 ms 856 KB Output is correct
9 Correct 2 ms 1112 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 39 ms 14128 KB Output is correct
14 Correct 27 ms 8516 KB Output is correct
15 Correct 19 ms 9304 KB Output is correct
16 Correct 20 ms 6232 KB Output is correct
17 Correct 120 ms 36188 KB Output is correct
18 Correct 80 ms 35672 KB Output is correct
19 Correct 102 ms 33624 KB Output is correct
20 Correct 68 ms 30812 KB Output is correct
21 Correct 208 ms 82716 KB Output is correct
22 Correct 207 ms 79832 KB Output is correct
23 Correct 228 ms 68756 KB Output is correct
24 Correct 190 ms 80728 KB Output is correct
25 Correct 390 ms 141556 KB Output is correct
26 Correct 575 ms 256852 KB Output is correct
27 Correct 690 ms 195424 KB Output is correct
28 Correct 745 ms 180700 KB Output is correct
29 Correct 699 ms 174252 KB Output is correct
30 Correct 705 ms 189752 KB Output is correct
31 Correct 439 ms 92004 KB Output is correct
32 Correct 653 ms 191524 KB Output is correct