oj.uz

Submission #876641

# Submission time Handle Problem Language Result Execution time Memory
876641 2023-11-22T06:37:12 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
91.25 / 100
 2000 ms 947616 KB 
#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'
#define pb emplace_back
#define front back
#define pop pop_back
#define push emplace_back

using namespace std;

int n, h, w;
const int MAXN = 16e6 + 1000;

string mat[4010];

vector<int> q[2];
vector<int> adj[MAXN];

bool tp[MAXN], used[MAXN];



int main(){
	ios::sync_with_stdio(0);cin.tie(0);

	cin >> h >> w;

	for(int i=0; i<h; i++) cin >> mat[i];


	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(mat[i][j] == '.') continue;

			int v = (i*w) + j;
			int u = (i+1)*w + j;

			if(i < (h-1) && mat[i+1][j] != '.'){
				adj[v].pb(u);
				adj[u].pb(v);
			}

			u = (i*w) + j + 1;
			if(j < (w-1) && mat[i][j+1] != '.'){
				adj[v].pb(u);
				adj[u].pb(v);
			}

			if(mat[i][j] == 'F') tp[v] = 0;
			else tp[v] = 1;
		}
	}



	int p, cnt=0;	
	if(mat[0][0] == 'F'){
		q[0].push(0);
		p = 0;
	}
	else{
		q[1].push(0);
		p = 1;
	}

	used[0] = 1;

	while(!q[0].empty() || !q[1].empty()){
		
		while(!q[p].empty()){
			int v = q[p].front();

			q[p].pop();
			
			for(int u : adj[v]){
				if(used[u]) continue;

				q[tp[u]].push(u);
				used[u] = 1;
			}
		}

		p ^= 1;
		cnt++;
	}

	cout << cnt << endl;

	return 0;

}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 386640 KB Output is correct
2 Correct 79 ms 378704 KB Output is correct
3 Correct 83 ms 378700 KB Output is correct
4 Correct 101 ms 384112 KB Output is correct
5 Correct 84 ms 379312 KB Output is correct
6 Correct 79 ms 378704 KB Output is correct
7 Correct 80 ms 378756 KB Output is correct
8 Correct 80 ms 378708 KB Output is correct
9 Correct 80 ms 378708 KB Output is correct
10 Correct 85 ms 379688 KB Output is correct
11 Correct 85 ms 380112 KB Output is correct
12 Correct 90 ms 381524 KB Output is correct
13 Correct 83 ms 379356 KB Output is correct
14 Correct 85 ms 379560 KB Output is correct
15 Correct 107 ms 384904 KB Output is correct
16 Correct 112 ms 386556 KB Output is correct
17 Correct 99 ms 382576 KB Output is correct
18 Correct 100 ms 384084 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 379220 KB Output is correct
2 Correct 173 ms 404396 KB Output is correct
3 Correct 547 ms 545100 KB Output is correct
4 Correct 222 ms 408404 KB Output is correct
5 Correct 498 ms 546384 KB Output is correct
6 Execution timed out 2078 ms 939372 KB Time limit exceeded
7 Correct 82 ms 378960 KB Output is correct
8 Correct 82 ms 379220 KB Output is correct
9 Correct 85 ms 379728 KB Output is correct
10 Correct 80 ms 378964 KB Output is correct
11 Correct 82 ms 378960 KB Output is correct
12 Correct 81 ms 378952 KB Output is correct
13 Correct 175 ms 404676 KB Output is correct
14 Correct 133 ms 392272 KB Output is correct
15 Correct 134 ms 391776 KB Output is correct
16 Correct 132 ms 390984 KB Output is correct
17 Correct 318 ms 442676 KB Output is correct
18 Correct 300 ms 425552 KB Output is correct
19 Correct 220 ms 408916 KB Output is correct
20 Correct 192 ms 417620 KB Output is correct
21 Correct 364 ms 477524 KB Output is correct
22 Correct 509 ms 546320 KB Output is correct
23 Correct 547 ms 504492 KB Output is correct
24 Correct 413 ms 499540 KB Output is correct
25 Correct 1518 ms 568108 KB Output is correct
26 Correct 1380 ms 833052 KB Output is correct
27 Correct 1957 ms 947616 KB Output is correct
28 Execution timed out 2056 ms 939696 KB Time limit exceeded
29 Execution timed out 2063 ms 933724 KB Time limit exceeded
30 Execution timed out 2056 ms 934952 KB Time limit exceeded
31 Correct 1709 ms 730384 KB Output is correct
32 Correct 1676 ms 859368 KB Output is correct