Submission #1186769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186769		Malix	Tracks in the Snow (BOI13_tracks)	C++20	100 / 100	971 ms	170628 KiB

tracks

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> ti;
typedef vector<ll> li;
typedef vector<li> lii;
 
#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define LSOne(s) ((s)&(-s))
 
ll INF=1000000000000000010;
int inf=1e9+10;
ll M=1e9+7;

int main() {   
// ios::sync_with_stdio(0);
// cin.tie(0);
    int n,m;cin>>n>>m;
    vii a(n,vi(m,0)),b(n,vi(m,0));
    REP(i,0,n)REP(j,0,m){
        char c;cin>>c;
        if(c=='F')a[i][j]=1;
        else if(c=='R')a[i][j]=2;
    }
    b[0][0]=1;
    deque<ti> pq;
    pq.push_back({1,0,0});
    vector<pi> loc={{1,0},{-1,0},{0,1},{0,-1}};
    int mx=1;
    while(!pq.empty()){
        int x=get<0>(pq.front());
        int y=get<1>(pq.front());
        int z=get<2>(pq.front());
        pq.pop_front();
        mx=max(mx,x);
        for(auto u:loc)if(y+u.F>=0&&y+u.F<n&&z+u.S>=0&z+u.S<m&&b[y+u.F][z+u.S]==0&&a[y+u.F][z+u.S]!=0){
            b[y+u.F][z+u.S]=b[y][z];
            if(a[y+u.F][z+u.S]!=a[y][z]){
                b[y+u.F][z+u.S]++;
                pq.push_back({b[y+u.F][z+u.S],y+u.F,z+u.S});
            }
            else pq.push_front({b[y+u.F][z+u.S],y+u.F,z+u.S});
        }
    }
    cout<<mx;
}

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