oj.uz

Submission #876640

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

#define endl '\n'
#define pb push_back
#define front back
#define pop pop_back
#define push push_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 113 ms 386764 KB Output is correct
2 Correct 81 ms 378736 KB Output is correct
3 Correct 81 ms 378684 KB Output is correct
4 Correct 100 ms 384064 KB Output is correct
5 Correct 85 ms 379472 KB Output is correct
6 Correct 82 ms 378708 KB Output is correct
7 Correct 81 ms 378960 KB Output is correct
8 Correct 83 ms 379224 KB Output is correct
9 Correct 79 ms 378812 KB Output is correct
10 Correct 86 ms 379980 KB Output is correct
11 Correct 85 ms 380056 KB Output is correct
12 Correct 91 ms 381644 KB Output is correct
13 Correct 84 ms 379388 KB Output is correct
14 Correct 83 ms 379472 KB Output is correct
15 Correct 105 ms 385424 KB Output is correct
16 Correct 114 ms 386644 KB Output is correct
17 Correct 98 ms 382640 KB Output is correct
18 Correct 103 ms 384260 KB Output is correct

Subtask #2
61.25 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 379464 KB Output is correct
2 Correct 174 ms 405328 KB Output is correct
3 Correct 555 ms 553680 KB Output is correct
4 Correct 239 ms 411004 KB Output is correct
5 Correct 509 ms 551568 KB Output is correct
6 Execution timed out 2082 ms 943260 KB Time limit exceeded
7 Correct 81 ms 379168 KB Output is correct
8 Correct 85 ms 379180 KB Output is correct
9 Correct 83 ms 379728 KB Output is correct
10 Correct 81 ms 378936 KB Output is correct
11 Correct 80 ms 378888 KB Output is correct
12 Correct 81 ms 378968 KB Output is correct
13 Correct 177 ms 404432 KB Output is correct
14 Correct 134 ms 392484 KB Output is correct
15 Correct 138 ms 391572 KB Output is correct
16 Correct 129 ms 390996 KB Output is correct
17 Correct 317 ms 442924 KB Output is correct
18 Correct 301 ms 425576 KB Output is correct
19 Correct 230 ms 408404 KB Output is correct
20 Correct 192 ms 417596 KB Output is correct
21 Correct 385 ms 477664 KB Output is correct
22 Correct 504 ms 546132 KB Output is correct
23 Correct 541 ms 504668 KB Output is correct
24 Correct 411 ms 499540 KB Output is correct
25 Correct 1487 ms 568088 KB Output is correct
26 Correct 1375 ms 833856 KB Output is correct
27 Correct 1973 ms 947944 KB Output is correct
28 Execution timed out 2096 ms 939984 KB Time limit exceeded
29 Execution timed out 2086 ms 935884 KB Time limit exceeded
30 Execution timed out 2062 ms 933796 KB Time limit exceeded
31 Correct 1685 ms 730244 KB Output is correct
32 Correct 1649 ms 859360 KB Output is correct