oj.uz

Submission #910717

# Submission time Handle Problem Language Result Execution time Memory
910717 2024-01-18T07:26:05 Z ByeWorld Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1090 ms 113572 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#define bupol __builtin_popcount
//#define int long long 
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
const int MAXN = 2e5+5;
const int MAXK = 205;
const int LOG = 20;
const int MOD = 1e9+7;
const int SQRT = 520;
const int INF = 1e9+10;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
vector <int> dx = {-1, 0, 0, 1};
vector <int> dy = {0, -1, 1, 0};

int h, w;
string s[4010];
int vis[4010][4010];

int ans, cnt, tot;
queue <pii> q[3]; // 'R', 'H'
char fnd;

void bfs(int ty){
    while(!q[ty].empty()){
        int x = q[ty].front().fi, y = q[ty].front().se;
        cnt++;
        //cout << x << ' ' << y << ' ' << ty << " p\n";
        q[ty].pop();

        for(int i=0; i<4; i++){
            int nx = x+dx[i], ny = y+dy[i];
            if(vis[nx][ny] || s[nx][ny] == '.') continue;
            vis[nx][ny] = 1; 

            if(s[nx][ny] == 'R') q[1].push({nx, ny});
            else q[2].push({nx, ny});
        }
    }
}

signed main(){
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> h >> w;
    for(int i=1; i<=h; i++){
        cin >> s[i];
        s[i] = '.'+s[i]+'.';
        for(int j=1; j<=w; j++)
            if(s[i][j]!='.') tot++;
    }
    //cout << tot << " t\n";
    for(int i=0; i<=w+1; i++){
        s[0] += '.'; s[h+1] += '.';
    }

    fnd = s[1][1]; vis[1][1] = 1; int te = 0; 
    //cout << fnd << " f\n";
    if(fnd=='R'){
        q[1].push({1, 1}); te = 1;
    } else {
        q[2].push({1, 1}); te = 2;
    }
    cnt = 0;
    while(cnt != tot){
        ans++;
        bfs(te);
        // if(fnd='F'){
        //     for(auto in : vec) cout << in.fi << ' '<< in.se << " p\n";
        //     exit(0);
        // }
        if(fnd=='R') fnd = 'H';
        else fnd = 'R';
        te = 3-te;
        //cout << cnt << ' ' << tot << " te\n";
    } 
    cout << ans << '\n';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 4180 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 8 ms 3676 KB Output is correct
5 Correct 5 ms 2008 KB Output is correct
6 Correct 1 ms 572 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 1112 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 3 ms 1884 KB Output is correct
11 Correct 3 ms 1624 KB Output is correct
12 Correct 6 ms 2140 KB Output is correct
13 Correct 4 ms 2140 KB Output is correct
14 Correct 4 ms 2120 KB Output is correct
15 Correct 13 ms 3932 KB Output is correct
16 Correct 14 ms 4152 KB Output is correct
17 Correct 11 ms 3932 KB Output is correct
18 Correct 10 ms 3672 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15964 KB Output is correct
2 Correct 60 ms 13136 KB Output is correct
3 Correct 375 ms 82292 KB Output is correct
4 Correct 107 ms 31648 KB Output is correct
5 Correct 237 ms 55688 KB Output is correct
6 Correct 1090 ms 113572 KB Output is correct
7 Correct 10 ms 16732 KB Output is correct
8 Correct 10 ms 15960 KB Output is correct
9 Correct 3 ms 940 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 10 ms 16300 KB Output is correct
12 Correct 2 ms 1116 KB Output is correct
13 Correct 57 ms 13188 KB Output is correct
14 Correct 34 ms 8516 KB Output is correct
15 Correct 27 ms 11096 KB Output is correct
16 Correct 30 ms 5576 KB Output is correct
17 Correct 160 ms 27584 KB Output is correct
18 Correct 110 ms 34644 KB Output is correct
19 Correct 112 ms 31536 KB Output is correct
20 Correct 87 ms 24492 KB Output is correct
21 Correct 239 ms 55180 KB Output is correct
22 Correct 223 ms 55648 KB Output is correct
23 Correct 302 ms 46036 KB Output is correct
24 Correct 221 ms 51780 KB Output is correct
25 Correct 489 ms 103252 KB Output is correct
26 Correct 503 ms 85884 KB Output is correct
27 Correct 710 ms 104792 KB Output is correct
28 Correct 1055 ms 113316 KB Output is correct
29 Correct 990 ms 111752 KB Output is correct
30 Correct 908 ms 109220 KB Output is correct
31 Correct 683 ms 76824 KB Output is correct
32 Correct 646 ms 103940 KB Output is correct