oj.uz

Submission #378369

# Submission time Handle Problem Language Result Execution time Memory
378369 2021-03-16T15:13:29 Z YJU Tracks in the Snow (BOI13_tracks) C++14
4.375 / 100
 2000 ms 688312 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;

char grid[N*N];
bitset<N*N> vis;
queue<ll> que;
vector<ll> nxt;
ll n,m,ans;

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

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)REP(j,m){
        while(1){
			grid[get(i,j)]=getchar();
			if(grid[get(i,j)]==' '||grid[get(i,j)]=='\n')continue;
			break;
        }
	}
	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.push_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 2112 ms 679284 KB Time limit exceeded
2 Execution timed out 2118 ms 401732 KB Time limit exceeded
3 Execution timed out 2082 ms 368024 KB Time limit exceeded
4 Execution timed out 2104 ms 210888 KB Time limit exceeded
5 Execution timed out 2111 ms 669544 KB Time limit exceeded
6 Execution timed out 2107 ms 393296 KB Time limit exceeded
7 Execution timed out 2105 ms 368220 KB Time limit exceeded
8 Execution timed out 2102 ms 362688 KB Time limit exceeded
9 Execution timed out 2067 ms 347720 KB Time limit exceeded
10 Execution timed out 2058 ms 455648 KB Time limit exceeded
11 Execution timed out 2082 ms 492 KB Time limit exceeded
12 Execution timed out 2115 ms 649440 KB Time limit exceeded
13 Execution timed out 2116 ms 669492 KB Time limit exceeded
14 Execution timed out 2116 ms 669508 KB Time limit exceeded
15 Execution timed out 2058 ms 651972 KB Time limit exceeded
16 Execution timed out 2127 ms 679108 KB Time limit exceeded
17 Execution timed out 2108 ms 393420 KB Time limit exceeded
18 Execution timed out 2087 ms 210924 KB Time limit exceeded

Subtask #2
4.375 / 70.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2090 ms 228176 KB Time limit exceeded
2 Execution timed out 2103 ms 642252 KB Time limit exceeded
3 Execution timed out 2119 ms 469444 KB Time limit exceeded
4 Execution timed out 2113 ms 388940 KB Time limit exceeded
5 Execution timed out 2072 ms 355528 KB Time limit exceeded
6 Execution timed out 2111 ms 340168 KB Time limit exceeded
7 Execution timed out 2070 ms 380124 KB Time limit exceeded
8 Execution timed out 2078 ms 227988 KB Time limit exceeded
9 Execution timed out 2121 ms 688312 KB Time limit exceeded
10 Execution timed out 2044 ms 204872 KB Time limit exceeded
11 Execution timed out 2083 ms 297344 KB Time limit exceeded
12 Execution timed out 2121 ms 345288 KB Time limit exceeded
13 Execution timed out 2091 ms 642116 KB Time limit exceeded
14 Execution timed out 2115 ms 654344 KB Time limit exceeded
15 Execution timed out 2106 ms 205324 KB Time limit exceeded
16 Execution timed out 2091 ms 504540 KB Time limit exceeded
17 Execution timed out 2121 ms 413984 KB Time limit exceeded
18 Execution timed out 2088 ms 233888 KB Time limit exceeded
19 Execution timed out 2121 ms 390948 KB Time limit exceeded
20 Execution timed out 2094 ms 504388 KB Time limit exceeded
21 Execution timed out 2116 ms 400100 KB Time limit exceeded
22 Execution timed out 2101 ms 355464 KB Time limit exceeded
23 Execution timed out 2129 ms 531156 KB Time limit exceeded
24 Execution timed out 2077 ms 213432 KB Time limit exceeded
25 Execution timed out 2095 ms 269460 KB Time limit exceeded
26 Correct 484 ms 14188 KB Output is correct
27 Correct 684 ms 20832 KB Output is correct
28 Execution timed out 2071 ms 218056 KB Time limit exceeded
29 Execution timed out 2101 ms 208936 KB Time limit exceeded
30 Execution timed out 2110 ms 215624 KB Time limit exceeded
31 Execution timed out 2125 ms 378564 KB Time limit exceeded
32 Execution timed out 2095 ms 286272 KB Time limit exceeded