oj.uz

Submission #1083776

# Submission time Handle Problem Language Result Execution time Memory
1083776 2024-09-04T06:25:10 Z altern23 Tracks in the Snow (BOI13_tracks) C++14
89.0625 / 100
 2000 ms 206700 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];
        }

        priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
        pq.push({1, {1, 1}});

        ll di[] = {0, 0, 1, -1}, dj[] = {1, -1, 0, 0};
        for(;!pq.empty();){
            auto x = pq.top(); pq.pop();
            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]);
                pq.push({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 36 ms 3160 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 22 ms 2392 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Correct 6 ms 1112 KB Output is correct
12 Correct 12 ms 1504 KB Output is correct
13 Correct 4 ms 1112 KB Output is correct
14 Correct 4 ms 1116 KB Output is correct
15 Correct 29 ms 3116 KB Output is correct
16 Correct 36 ms 3164 KB Output is correct
17 Correct 20 ms 2904 KB Output is correct
18 Correct 23 ms 2392 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1116 KB Output is correct
2 Correct 111 ms 15972 KB Output is correct
3 Correct 431 ms 157264 KB Output is correct
4 Correct 135 ms 37316 KB Output is correct
5 Correct 222 ms 88660 KB Output is correct
6 Execution timed out 2033 ms 206700 KB Time limit exceeded
7 Correct 1 ms 856 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 4 ms 1372 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 860 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 107 ms 15980 KB Output is correct
14 Correct 58 ms 9304 KB Output is correct
15 Correct 21 ms 10072 KB Output is correct
16 Correct 50 ms 6748 KB Output is correct
17 Correct 272 ms 40272 KB Output is correct
18 Correct 89 ms 39540 KB Output is correct
19 Correct 148 ms 37204 KB Output is correct
20 Correct 108 ms 34264 KB Output is correct
21 Correct 265 ms 92072 KB Output is correct
22 Correct 225 ms 88656 KB Output is correct
23 Correct 537 ms 76628 KB Output is correct
24 Correct 179 ms 89424 KB Output is correct
25 Correct 446 ms 157160 KB Output is correct
26 Correct 1034 ms 120660 KB Output is correct
27 Execution timed out 2043 ms 163516 KB Time limit exceeded
28 Execution timed out 2065 ms 206472 KB Time limit exceeded
29 Execution timed out 2080 ms 181944 KB Time limit exceeded
30 Execution timed out 2044 ms 178724 KB Time limit exceeded
31 Correct 1802 ms 102604 KB Output is correct
32 Correct 1997 ms 160452 KB Output is correct