Submission #1129795

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129795		wb11111	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	1089 ms	154824 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i= 0; i<(n); i++)
#define reps(i,s, n) for(int i= (s); i<(n); i++)
#define each(a, x) for (auto &a : x)
#define vv(T) vector<T>
#define endl '\n'
#define sz(x) (int)x.size()
#define ll long long
#define all(c) begin(c), end(c)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define wr cout<<
#define wre wr endl;
#define wrut(a) {each(i,(a))wr i; wre}
#define wrot(a,b,c) {wre wr a<<" "<<b<<" "<<c; wre}
// #define int ll
// const int mod=1e9+7;
// const int maxn=(1e3)*3+7;
// int dp[maxn][maxn];
int dx[4]{1,-1,0,0},dy[4]{0,0,1,-1};
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n,m;
    cin>>n>>m;
    char c;
    vv(vv(int)) a(n+2,vv(int)(m+2,0)),depth(n+2,vv(int)(m+2,0));
    vv(vv(bool)) vis(n+2,vv(bool)(m+2,1));
    rep(i,n){
        rep(j,m){
            cin>>c;
            if(c=='R'){
                a[i+1][j+1]=1;
                vis[i+1][j+1]=0;
            } else if(c=='F'){
                a[i+1][j+1]=2;
                vis[i+1][j+1]=0;
            }
        }
    }
    int s=0;
    depth[1][1]=1;
    deque<pair<int,int>> q;
    q.push_front({1,1});
    vis[1][1]=1;
    while(!q.empty()){
        pair<int,int> p=q.front();
        q.pop_front();
        s=max(s,depth[p.fi][p.se]);
        rep(i,4){
            int x=p.fi+dx[i],y=p.se+dy[i];
            if(a[x][y]==a[p.fi][p.se]&&!vis[x][y]){
                depth[x][y]=depth[p.fi][p.se];
                vis[x][y]=1;
                q.push_front({x,y});
            } else if(!vis[x][y]){
                depth[x][y]=depth[p.fi][p.se]+1;
                vis[x][y]=1;
                q.push_back({x,y});
            }
        }
    }
    wr s;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70