oj.uz

Submission #1115081

# Submission time Handle Problem Language Result Execution time Memory
1115081 2024-11-20T03:00:44 Z DON_F Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 401 ms 89996 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define all(x) x.begin(), x.end()
#define L(i, b, e) for (int i = b; i < e; ++i)
#define R(i, b, e) for (int i = b; i >= e; --i)
#define pb emplace_back
#define vi vector<int>
#define sz(x) ((int) x.size())
const int N = 4e3 + 7, Mx = 1e9 + 9;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int n, m;
string s[N];
bool vis[N][N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    L(i, 0, n){
        cin >> s[i];
    }
    auto in = [&](int x, int y){
        return (x >= 0 && y >= 0 && x < n && y < m);
    };
    int ans = 1;
    char lst = s[0][0];
    deque<pair<int, int>> dq;
    dq.push_back({0, 0});
    vis[0][0] = true;
    while (!dq.empty()){
        pair<int, int> t = dq.front();
        dq.pop_front();
        if (s[t.first][t.second] != lst){
            lst = s[t.first][t.second];
            ++ans;
        }
        L(i, 0, 4){
            int nx = t.first + dx[i], ny = t.second + dy[i];
            if (in(nx, ny) && vis[nx][ny] == false && s[nx][ny] != '.'){
                if (s[nx][ny] == s[t.first][t.second])dq.push_front({nx, ny});
                else dq.push_back({nx, ny});
                vis[nx][ny] = true;
            }
        }
    }
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2896 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 708 KB Output is correct
4 Correct 5 ms 2896 KB Output is correct
5 Correct 3 ms 1872 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 592 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 3 ms 1784 KB Output is correct
11 Correct 2 ms 1380 KB Output is correct
12 Correct 4 ms 1872 KB Output is correct
13 Correct 3 ms 1872 KB Output is correct
14 Correct 2 ms 1872 KB Output is correct
15 Correct 7 ms 2896 KB Output is correct
16 Correct 8 ms 2896 KB Output is correct
17 Correct 6 ms 2764 KB Output is correct
18 Correct 5 ms 2896 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15440 KB Output is correct
2 Correct 25 ms 8540 KB Output is correct
3 Correct 149 ms 49632 KB Output is correct
4 Correct 38 ms 15524 KB Output is correct
5 Correct 125 ms 30672 KB Output is correct
6 Correct 365 ms 63112 KB Output is correct
7 Correct 12 ms 16208 KB Output is correct
8 Correct 11 ms 15560 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 11 ms 15952 KB Output is correct
12 Correct 2 ms 1104 KB Output is correct
13 Correct 26 ms 8528 KB Output is correct
14 Correct 16 ms 5844 KB Output is correct
15 Correct 13 ms 6480 KB Output is correct
16 Correct 13 ms 3408 KB Output is correct
17 Correct 67 ms 16712 KB Output is correct
18 Correct 45 ms 16344 KB Output is correct
19 Correct 40 ms 15448 KB Output is correct
20 Correct 36 ms 14360 KB Output is correct
21 Correct 98 ms 31816 KB Output is correct
22 Correct 126 ms 30792 KB Output is correct
23 Correct 129 ms 26184 KB Output is correct
24 Correct 100 ms 31392 KB Output is correct
25 Correct 227 ms 49560 KB Output is correct
26 Correct 218 ms 89996 KB Output is correct
27 Correct 276 ms 76096 KB Output is correct
28 Correct 369 ms 63056 KB Output is correct
29 Correct 401 ms 61532 KB Output is correct
30 Correct 335 ms 66672 KB Output is correct
31 Correct 281 ms 34632 KB Output is correct
32 Correct 231 ms 64768 KB Output is correct