oj.uz

Submission #1081713

# Submission time Handle Problem Language Result Execution time Memory
1081713 2024-08-30T09:30:54 Z aletra Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1298 ms 917328 KB 
#include <bits/stdc++.h>
using namespace std;

#undef _GLIBCXX_DEBUG

#define rep(i, a, b) for(ll i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;

vector<vector<char>> grid;
ll visited[4010][4010];
ll H, W;
vector<pair<ll,ll>> q;
vector<pair<ll,ll>> q2;

ll dfs(ll row, ll col, char curr){
    if (row >= H || col >= W || col < 0 || row <0) return 0;
    if (visited[row][col] == 1) return 0;
    if (grid[row][col] =='.') return 0;
    if (grid[row][col] != curr){
        q2.push_back(make_pair(row,col));
        //cout << "in bfs " << row << " " << col << "\n";
        return 0;
    }
    visited[row][col] = 1;
    
    dfs(row+1, col,curr);
    dfs(row-1, col,curr);
    dfs(row, col+1,curr);
    dfs(row, col-1,curr);
    return 0;
}

int main(){
    //cin.tie(0)->sync_with_stdio(0);
    memset(visited, 0, sizeof(visited));
    cin >>H >> W;
    grid.resize(H, vector<char>(W));
    char temp;
    rep(i,0,H)
        rep (j,0,W){
            cin >> temp;
            grid[i][j] = temp;
        }
    char ani = grid[0][0];


    q.push_back(make_pair(0,0));
    
    
    ll cnt =0;
    while (q.size()){
        

        while(!q.empty()){
            pll s = q.back();
            q.pop_back();

            dfs(s.first, s.second, grid[s.first][s.second]);
            


        }
        //cout << "new q " << "\n";
        cnt ++;
        swap(q, q2);
        q2.clear();
        if (ani == 'R') ani = 'F';
        if (ani == 'F') ani = 'R';
    }
    cout << cnt << "\n";
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 127496 KB Output is correct
2 Correct 45 ms 126036 KB Output is correct
3 Correct 46 ms 126292 KB Output is correct
4 Correct 62 ms 128448 KB Output is correct
5 Correct 47 ms 126288 KB Output is correct
6 Correct 42 ms 126292 KB Output is correct
7 Correct 42 ms 126296 KB Output is correct
8 Correct 49 ms 126292 KB Output is correct
9 Correct 43 ms 126284 KB Output is correct
10 Correct 48 ms 126356 KB Output is correct
11 Correct 44 ms 126804 KB Output is correct
12 Correct 49 ms 126660 KB Output is correct
13 Correct 53 ms 126556 KB Output is correct
14 Correct 47 ms 126508 KB Output is correct
15 Correct 61 ms 127172 KB Output is correct
16 Correct 62 ms 127436 KB Output is correct
17 Correct 59 ms 126776 KB Output is correct
18 Correct 55 ms 128456 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 126636 KB Output is correct
2 Correct 114 ms 129620 KB Output is correct
3 Correct 622 ms 158208 KB Output is correct
4 Correct 186 ms 133972 KB Output is correct
5 Correct 473 ms 144208 KB Output is correct
6 Correct 1198 ms 259700 KB Output is correct
7 Correct 45 ms 126804 KB Output is correct
8 Correct 48 ms 126548 KB Output is correct
9 Correct 47 ms 126804 KB Output is correct
10 Correct 46 ms 126592 KB Output is correct
11 Correct 47 ms 126552 KB Output is correct
12 Correct 43 ms 126288 KB Output is correct
13 Correct 114 ms 129528 KB Output is correct
14 Correct 91 ms 128344 KB Output is correct
15 Correct 84 ms 128340 KB Output is correct
16 Correct 98 ms 127860 KB Output is correct
17 Correct 230 ms 134740 KB Output is correct
18 Correct 216 ms 134228 KB Output is correct
19 Correct 213 ms 133836 KB Output is correct
20 Correct 178 ms 133200 KB Output is correct
21 Correct 392 ms 144980 KB Output is correct
22 Correct 404 ms 144356 KB Output is correct
23 Correct 424 ms 142220 KB Output is correct
24 Correct 384 ms 144360 KB Output is correct
25 Correct 700 ms 158300 KB Output is correct
26 Correct 1298 ms 917328 KB Output is correct
27 Correct 1160 ms 365756 KB Output is correct
28 Correct 1142 ms 259696 KB Output is correct
29 Correct 1096 ms 252448 KB Output is correct
30 Correct 1072 ms 304260 KB Output is correct
31 Correct 739 ms 150352 KB Output is correct
32 Correct 1149 ms 380752 KB Output is correct