oj.uz

Submission #364120

# Submission time Handle Problem Language Result Execution time Memory
364120 2021-02-08T09:11:10 Z rocks03 Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 992 ms 122748 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int H, W;
vector<vector<char>> a;

int dx[] = {-1, +1, 0, 0};
int dy[] = {0, 0, -1, +1};
bool valid(int x, int y){
    return (x >= 0 && x < H && y >= 0 && y < W && a[x][y] != '.');
}

void solve(){
    cin >> H >> W;
    a = vector<vector<char>>(H, vector<char>(W));
    rep(i, 0, H){
        string s; cin >> s;
        rep(j, 0, W){
            a[i][j] = s[j];
        }
    }
    deque<pii> q;
    q.push_front({0, 0});
    vector<vector<int>> d(H, vector<int>(W, INT_MAX));
    d[0][0] = 1;
    int ans = 1;
    while(!q.empty()){
        auto [x, y] = q.front();
        q.pop_front();
        rep(i, 0, 4){
            int x2 = x + dx[i], y2 = y + dy[i];
            if(valid(x2, y2)){
                if(a[x2][y2] != a[x][y] && d[x2][y2] > d[x][y] + 1){
                    d[x2][y2] = d[x][y] + 1;
                    q.push_back({x2, y2});
                } else if(a[x2][y2] == a[x][y] && d[x2][y2] > d[x][y]){
                    d[x2][y2] = d[x][y];
                    q.push_front({x2, y2});
                }
            }
        }
        ans = max(ans, d[x][y]);
    }
    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

Compilation message

tracks.cpp: In function 'void solve()':
tracks.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |         auto [x, y] = q.front();
      |              ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 2028 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 10 ms 1516 KB Output is correct
5 Correct 3 ms 876 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 7 ms 876 KB Output is correct
13 Correct 4 ms 876 KB Output is correct
14 Correct 3 ms 876 KB Output is correct
15 Correct 14 ms 1900 KB Output is correct
16 Correct 18 ms 1900 KB Output is correct
17 Correct 10 ms 1772 KB Output is correct
18 Correct 10 ms 1536 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 56 ms 9836 KB Output is correct
3 Correct 339 ms 94700 KB Output is correct
4 Correct 85 ms 22508 KB Output is correct
5 Correct 213 ms 53612 KB Output is correct
6 Correct 977 ms 108168 KB Output is correct
7 Correct 3 ms 1132 KB Output is correct
8 Correct 2 ms 876 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 55 ms 9708 KB Output is correct
14 Correct 40 ms 5740 KB Output is correct
15 Correct 30 ms 6380 KB Output is correct
16 Correct 28 ms 4204 KB Output is correct
17 Correct 145 ms 24328 KB Output is correct
18 Correct 118 ms 24044 KB Output is correct
19 Correct 93 ms 22636 KB Output is correct
20 Correct 76 ms 20716 KB Output is correct
21 Correct 189 ms 55276 KB Output is correct
22 Correct 240 ms 53484 KB Output is correct
23 Correct 296 ms 46188 KB Output is correct
24 Correct 187 ms 53996 KB Output is correct
25 Correct 536 ms 94728 KB Output is correct
26 Correct 606 ms 122748 KB Output is correct
27 Correct 795 ms 112304 KB Output is correct
28 Correct 970 ms 107904 KB Output is correct
29 Correct 992 ms 108280 KB Output is correct
30 Correct 969 ms 107248 KB Output is correct
31 Correct 860 ms 61248 KB Output is correct
32 Correct 714 ms 110304 KB Output is correct