Submission #378374

#	Time	Username	Problem	Language	Result	Execution time	Memory
378374		YJU	Tracks in the Snow (BOI13_tracks)	C++14	56.25 / 100	2092 ms	14704 KiB

tracks

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef int ll;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define mp make_pair
#define REP(i,n) for(int i=0;i<n;i++)
const ll N=4e3;

string grid,s;
bitset<N*N> vis;
queue<ll> que;
vector<ll> nxt;
ll n,m,ans;

inline ll get(ll r,ll c){
	return r*m+c;
}

inline ll dest(ll now,ll dir){
	if(dir==0)return (now/m==0?-1:now-m);
	if(dir==1)return (now%m==0?-1:now-1);
	if(dir==2)return (now/m==n-1?-1:now+m);
	if(dir==3)return (now%m==m-1?-1:now+1);
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;
	REP(i,n){
		cin>>s;
		grid=grid+s;
	}
	que.push(get(0,0));vis[get(0,0)]=1;
	que.push(get(n-1,m-1));vis[get(n-1,m-1)]=1;
	for(char i=grid[get(0,0)];;i=(i=='F'?'R':'F')){
		nxt.clear();
		++ans;
		assert(ans<=n*m);
		while(!(que.empty())){
            ll nd=que.front();que.pop();
            for(int j=0;j<4;j++){
				ll to=dest(nd,j);
				if(to==-1||vis[to])continue;
				if(grid[to]==i){
					vis[to]=1;
					que.push(to);
				}else if(grid[to]!='.'){
					vis[to]=1;
                    nxt.emplace_back(to);
				}
            }
		}
		if((ll)nxt.size()==0)break;
		for(ll j:nxt)que.push(j);
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message (stderr)

tracks.cpp: In function 'll dest(ll, ll)':
tracks.cpp:27:1: warning: control reaches end of non-void function [-Wreturn-type]
   27 | }
      | ^

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