Submission #876614

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876614	2023-11-22T05:36:01 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	86.875 / 100	2000 ms	1045716 KB

tracks

#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'
#define pb push_back

using namespace std;

int n, h, w;
const int MAXN = 2e7;

string mat[4000];

queue<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);
			}

			tp[v] = (mat[i][j] == 'F')? 0 : 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	176 ms	482196 KB	Output is correct
2	Correct	101 ms	474240 KB	Output is correct
3	Correct	100 ms	474192 KB	Output is correct
4	Correct	135 ms	479524 KB	Output is correct
5	Correct	103 ms	474960 KB	Output is correct
6	Correct	101 ms	474100 KB	Output is correct
7	Correct	99 ms	474192 KB	Output is correct
8	Correct	99 ms	474452 KB	Output is correct
9	Correct	101 ms	474288 KB	Output is correct
10	Correct	106 ms	475328 KB	Output is correct
11	Correct	105 ms	475652 KB	Output is correct
12	Correct	111 ms	477012 KB	Output is correct
13	Correct	103 ms	475036 KB	Output is correct
14	Correct	102 ms	474960 KB	Output is correct
15	Correct	126 ms	480700 KB	Output is correct
16	Correct	140 ms	482192 KB	Output is correct
17	Correct	116 ms	478292 KB	Output is correct
18	Correct	119 ms	479604 KB	Output is correct

Subtask #2

56.875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	102 ms	474708 KB	Output is correct
2	Correct	199 ms	501524 KB	Output is correct
3	Correct	573 ms	659540 KB	Output is correct
4	Correct	226 ms	507576 KB	Output is correct
5	Correct	530 ms	650796 KB	Output is correct
6	Execution timed out	2087 ms	1044916 KB	Time limit exceeded
7	Correct	102 ms	474708 KB	Output is correct
8	Correct	101 ms	474708 KB	Output is correct
9	Correct	103 ms	475220 KB	Output is correct
10	Correct	103 ms	474444 KB	Output is correct
11	Correct	101 ms	474448 KB	Output is correct
12	Correct	104 ms	474704 KB	Output is correct
13	Correct	199 ms	501316 KB	Output is correct
14	Correct	155 ms	488788 KB	Output is correct
15	Correct	155 ms	486224 KB	Output is correct
16	Correct	153 ms	487128 KB	Output is correct
17	Correct	352 ms	542288 KB	Output is correct
18	Correct	328 ms	525072 KB	Output is correct
19	Correct	226 ms	507716 KB	Output is correct
20	Correct	214 ms	516576 KB	Output is correct
21	Correct	380 ms	582152 KB	Output is correct
22	Correct	526 ms	650660 KB	Output is correct
23	Correct	613 ms	608100 KB	Output is correct
24	Correct	408 ms	603940 KB	Output is correct
25	Correct	1499 ms	682600 KB	Output is correct
26	Correct	1816 ms	907644 KB	Output is correct
27	Execution timed out	2033 ms	1041624 KB	Time limit exceeded
28	Execution timed out	2111 ms	1045716 KB	Time limit exceeded
29	Execution timed out	2064 ms	1044804 KB	Time limit exceeded
30	Execution timed out	2088 ms	1030908 KB	Time limit exceeded
31	Correct	1763 ms	835552 KB	Output is correct
32	Execution timed out	2098 ms	956688 KB	Time limit exceeded