oj.uz

Submission #1120895

# Submission time Handle Problem Language Result Execution time Memory
1120895 2024-11-28T09:22:56 Z Haciyev12 Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1799 ms 311500 KB 
#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pb push_back
#define in insert
#define F first
#define S second
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#define endl '\n'
#define pii pair<ll,ll>
using namespace std;
const ll INF =1e18, mod = 1e9 + 7, N = 3e5 + 5;
ll n,m;
ll a[4005][4005];
ll st;
ll ans = 0;
queue<pii>q;
ll dx[4] = {-1,1, 0, 0};
ll dy[4] = {0, 0, -1, 1};
ll used[4005][4005];
vector<pii>q1;
bool test;
void ch(){
     test = false;
    while(!q.empty()){
        ll x = q.front().F;
        ll y = q.front().S;
        q.pop();
        if(used[x][y] == 1){
            continue;
        }
        used[x][y] = 1;
        for(int i = 0; i < 4; i++){
            ll nx = x + dx[i];
            ll ny = y + dy[i];
            if(nx < 0 || nx >= n || ny < 0 || ny >= m){
                continue;
            }
            if(used[nx][ny] == 0 && st == a[nx][ny]){
                q.push({nx,ny});
            }
            else if(used[nx][ny] == 0 && -st == a[nx][ny]){
                q1.pb({nx,ny});//check again
                test = true;
            }
        }

    }



    if(test){
            ans++;
            for(int i = 0; i < q1.size(); i++){
                q.push({q1[i].F,q1[i].S});
            }
            q1.clear();
            st = -st;//swap
            ch();
    }
}
/*
   x
  y 0 z
    a
*/
void solve(){
    cin >> n >> m;
    char c;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> c;
            if(c == 'R'){
                a[i][j] = 1;
            }
            else if(c == 'F'){
                a[i][j] = -1;
            }
        }
    }
    st = a[0][0];
    q.push({0,0});
    ch();
    cout << ans + 1<< endl;
}
int main(){
    fast;
    solve();
    return 0;
}

Compilation message

tracks.cpp: In function 'void ch()':
tracks.cpp:55:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int i = 0; i < q1.size(); i++){
      |                            ~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 8480 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 848 KB Output is correct
4 Correct 16 ms 7616 KB Output is correct
5 Correct 5 ms 3664 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 1 ms 848 KB Output is correct
8 Correct 3 ms 848 KB Output is correct
9 Correct 2 ms 1360 KB Output is correct
10 Correct 5 ms 2896 KB Output is correct
11 Correct 5 ms 2896 KB Output is correct
12 Correct 11 ms 4300 KB Output is correct
13 Correct 5 ms 3664 KB Output is correct
14 Correct 6 ms 3664 KB Output is correct
15 Correct 29 ms 7504 KB Output is correct
16 Correct 33 ms 8560 KB Output is correct
17 Correct 19 ms 7936 KB Output is correct
18 Correct 14 ms 7464 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31824 KB Output is correct
2 Correct 90 ms 23368 KB Output is correct
3 Correct 401 ms 119624 KB Output is correct
4 Correct 140 ms 70728 KB Output is correct
5 Correct 284 ms 100940 KB Output is correct
6 Correct 1799 ms 311500 KB Output is correct
7 Correct 25 ms 33360 KB Output is correct
8 Correct 27 ms 31824 KB Output is correct
9 Correct 4 ms 1376 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 34 ms 32592 KB Output is correct
12 Correct 3 ms 1872 KB Output is correct
13 Correct 89 ms 23292 KB Output is correct
14 Correct 52 ms 15836 KB Output is correct
15 Correct 48 ms 23884 KB Output is correct
16 Correct 49 ms 9916 KB Output is correct
17 Correct 228 ms 49028 KB Output is correct
18 Correct 197 ms 78940 KB Output is correct
19 Correct 138 ms 70728 KB Output is correct
20 Correct 101 ms 40092 KB Output is correct
21 Correct 277 ms 83524 KB Output is correct
22 Correct 304 ms 101128 KB Output is correct
23 Correct 496 ms 80200 KB Output is correct
24 Correct 265 ms 80884 KB Output is correct
25 Correct 824 ms 251208 KB Output is correct
26 Correct 967 ms 219856 KB Output is correct
27 Correct 1053 ms 260956 KB Output is correct
28 Correct 1670 ms 311420 KB Output is correct
29 Correct 1753 ms 302636 KB Output is correct
30 Correct 1328 ms 296808 KB Output is correct
31 Correct 1204 ms 189632 KB Output is correct
32 Correct 836 ms 259176 KB Output is correct