Submission #910717

#	Time	Username	Problem	Language	Result	Execution time	Memory
910717		ByeWorld	Tracks in the Snow (BOI13_tracks)	C++14	100 / 100	1090 ms	113572 KiB

tracks

#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 / 30
• Subtask 2: 70 / 70