oj.uz

Submission #378371

# Submission time Handle Problem Language Result Execution time Memory
378371 2021-03-16T15:18:54 Z YJU Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 2000 ms 688208 KB 
#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;
		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]!='.'){
                    nxt.emplace_back(to);
				}
            }
		}
		if((ll)nxt.size()==0)break;
		for(ll j:nxt)que.push(j);
	}
	cout<<ans<<"\n";
	return 0;
}

Compilation message

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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 679180 KB Time limit exceeded
2 Execution timed out 2118 ms 386748 KB Time limit exceeded
3 Execution timed out 2124 ms 368048 KB Time limit exceeded
4 Execution timed out 2065 ms 203188 KB Time limit exceeded
5 Execution timed out 2120 ms 666988 KB Time limit exceeded
6 Execution timed out 2119 ms 399276 KB Time limit exceeded
7 Execution timed out 2115 ms 367996 KB Time limit exceeded
8 Execution timed out 2115 ms 362552 KB Time limit exceeded
9 Execution timed out 2106 ms 347736 KB Time limit exceeded
10 Execution timed out 2124 ms 455900 KB Time limit exceeded
11 Execution timed out 2070 ms 620 KB Time limit exceeded
12 Execution timed out 2125 ms 649216 KB Time limit exceeded
13 Execution timed out 2100 ms 669576 KB Time limit exceeded
14 Execution timed out 2114 ms 669476 KB Time limit exceeded
15 Execution timed out 2112 ms 672804 KB Time limit exceeded
16 Execution timed out 2102 ms 679404 KB Time limit exceeded
17 Execution timed out 2128 ms 393596 KB Time limit exceeded
18 Execution timed out 2104 ms 210528 KB Time limit exceeded

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2107 ms 227928 KB Time limit exceeded
2 Execution timed out 2102 ms 379764 KB Time limit exceeded
3 Execution timed out 2031 ms 14948 KB Time limit exceeded
4 Execution timed out 2055 ms 11960 KB Time limit exceeded
5 Execution timed out 2062 ms 13884 KB Time limit exceeded
6 Execution timed out 2072 ms 15668 KB Time limit exceeded
7 Execution timed out 2056 ms 257164 KB Time limit exceeded
8 Execution timed out 2087 ms 228248 KB Time limit exceeded
9 Execution timed out 2110 ms 688208 KB Time limit exceeded
10 Execution timed out 2112 ms 205340 KB Time limit exceeded
11 Execution timed out 2070 ms 234732 KB Time limit exceeded
12 Execution timed out 2082 ms 345420 KB Time limit exceeded
13 Execution timed out 2112 ms 380240 KB Time limit exceeded
14 Execution timed out 2119 ms 420712 KB Time limit exceeded
15 Execution timed out 2067 ms 187336 KB Time limit exceeded
16 Execution timed out 2134 ms 504844 KB Time limit exceeded
17 Execution timed out 2025 ms 12176 KB Time limit exceeded
18 Execution timed out 2089 ms 12100 KB Time limit exceeded
19 Execution timed out 2062 ms 11500 KB Time limit exceeded
20 Execution timed out 2054 ms 11096 KB Time limit exceeded
21 Execution timed out 2068 ms 12936 KB Time limit exceeded
22 Execution timed out 2075 ms 13520 KB Time limit exceeded
23 Execution timed out 2069 ms 13032 KB Time limit exceeded
24 Execution timed out 2074 ms 13840 KB Time limit exceeded
25 Execution timed out 2070 ms 15260 KB Time limit exceeded
26 Execution timed out 2091 ms 14188 KB Time limit exceeded
27 Execution timed out 2091 ms 14556 KB Time limit exceeded
28 Execution timed out 2044 ms 14792 KB Time limit exceeded
29 Execution timed out 2058 ms 14916 KB Time limit exceeded
30 Execution timed out 2015 ms 14632 KB Time limit exceeded
31 Execution timed out 2069 ms 13160 KB Time limit exceeded
32 Execution timed out 2067 ms 14840 KB Time limit exceeded