Submission #876615

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
876615	2023-11-22T05:40:27 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++14	86.875 / 100	2000 ms	931212 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 = 16e6 + 1000;

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	147 ms	386620 KB	Output is correct
2	Correct	79 ms	378740 KB	Output is correct
3	Correct	82 ms	378708 KB	Output is correct
4	Correct	99 ms	383832 KB	Output is correct
5	Correct	85 ms	379472 KB	Output is correct
6	Correct	81 ms	378704 KB	Output is correct
7	Correct	83 ms	378708 KB	Output is correct
8	Correct	81 ms	378844 KB	Output is correct
9	Correct	80 ms	378708 KB	Output is correct
10	Correct	84 ms	379476 KB	Output is correct
11	Correct	84 ms	379984 KB	Output is correct
12	Correct	93 ms	381500 KB	Output is correct
13	Correct	84 ms	379304 KB	Output is correct
14	Correct	82 ms	379472 KB	Output is correct
15	Correct	102 ms	384852 KB	Output is correct
16	Correct	111 ms	386384 KB	Output is correct
17	Correct	95 ms	382556 KB	Output is correct
18	Correct	99 ms	383828 KB	Output is correct

Subtask #2

56.875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	85 ms	379216 KB	Output is correct
2	Correct	175 ms	404408 KB	Output is correct
3	Correct	532 ms	545012 KB	Output is correct
4	Correct	202 ms	408412 KB	Output is correct
5	Correct	493 ms	546444 KB	Output is correct
6	Execution timed out	2061 ms	930356 KB	Time limit exceeded
7	Correct	87 ms	378968 KB	Output is correct
8	Correct	82 ms	379056 KB	Output is correct
9	Correct	88 ms	379988 KB	Output is correct
10	Correct	81 ms	378964 KB	Output is correct
11	Correct	81 ms	378852 KB	Output is correct
12	Correct	80 ms	378964 KB	Output is correct
13	Correct	174 ms	404412 KB	Output is correct
14	Correct	134 ms	392476 KB	Output is correct
15	Correct	147 ms	391760 KB	Output is correct
16	Correct	130 ms	390996 KB	Output is correct
17	Correct	326 ms	442884 KB	Output is correct
18	Correct	297 ms	425552 KB	Output is correct
19	Correct	206 ms	408656 KB	Output is correct
20	Correct	184 ms	417616 KB	Output is correct
21	Correct	344 ms	477576 KB	Output is correct
22	Correct	493 ms	546324 KB	Output is correct
23	Correct	571 ms	504696 KB	Output is correct
24	Correct	375 ms	499372 KB	Output is correct
25	Correct	1509 ms	568124 KB	Output is correct
26	Correct	1762 ms	799972 KB	Output is correct
27	Execution timed out	2069 ms	927056 KB	Time limit exceeded
28	Execution timed out	2081 ms	931212 KB	Time limit exceeded
29	Execution timed out	2071 ms	930572 KB	Time limit exceeded
30	Execution timed out	2049 ms	919356 KB	Time limit exceeded
31	Correct	1687 ms	730320 KB	Output is correct
32	Execution timed out	2048 ms	842484 KB	Time limit exceeded