답안 #876628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876628	2023-11-22T06:22:35 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	86.875 / 100	2000 ms	939532 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[4010];

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

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



	int p, cnt=0;	
	if(mat[0][0] == 'F'){
		q[0].emplace(0);
		p = 0;
	}
	else{
		q[1].emplace(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]].emplace(u);
				used[u] = 1;
			}
		}

		p ^= 1;
		cnt++;
	}

	cout << cnt << endl;

	return 0;

}

Subtask #1

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	182 ms	386388 KB	Output is correct
2	Correct	81 ms	378708 KB	Output is correct
3	Correct	81 ms	378708 KB	Output is correct
4	Correct	101 ms	383848 KB	Output is correct
5	Correct	84 ms	379496 KB	Output is correct
6	Correct	81 ms	378736 KB	Output is correct
7	Correct	81 ms	378704 KB	Output is correct
8	Correct	82 ms	378964 KB	Output is correct
9	Correct	80 ms	378684 KB	Output is correct
10	Correct	84 ms	379472 KB	Output is correct
11	Correct	85 ms	380092 KB	Output is correct
12	Correct	92 ms	381408 KB	Output is correct
13	Correct	89 ms	377564 KB	Output is correct
14	Correct	85 ms	379472 KB	Output is correct
15	Correct	104 ms	384852 KB	Output is correct
16	Correct	114 ms	386488 KB	Output is correct
17	Correct	97 ms	382548 KB	Output is correct
18	Correct	100 ms	383876 KB	Output is correct

Subtask #2

56.875 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	379224 KB	Output is correct
2	Correct	180 ms	404304 KB	Output is correct
3	Correct	611 ms	545036 KB	Output is correct
4	Correct	208 ms	410452 KB	Output is correct
5	Correct	513 ms	550832 KB	Output is correct
6	Execution timed out	2045 ms	938140 KB	Time limit exceeded
7	Correct	81 ms	379220 KB	Output is correct
8	Correct	83 ms	379216 KB	Output is correct
9	Correct	84 ms	379728 KB	Output is correct
10	Correct	82 ms	378956 KB	Output is correct
11	Correct	81 ms	378960 KB	Output is correct
12	Correct	81 ms	379076 KB	Output is correct
13	Correct	181 ms	405296 KB	Output is correct
14	Correct	139 ms	393044 KB	Output is correct
15	Correct	136 ms	392556 KB	Output is correct
16	Correct	138 ms	391504 KB	Output is correct
17	Correct	344 ms	445184 KB	Output is correct
18	Correct	308 ms	427888 KB	Output is correct
19	Correct	208 ms	410608 KB	Output is correct
20	Correct	194 ms	419692 KB	Output is correct
21	Correct	371 ms	482312 KB	Output is correct
22	Correct	501 ms	550936 KB	Output is correct
23	Correct	597 ms	508752 KB	Output is correct
24	Correct	399 ms	504004 KB	Output is correct
25	Correct	1522 ms	576340 KB	Output is correct
26	Correct	1786 ms	806116 KB	Output is correct
27	Execution timed out	2052 ms	935080 KB	Time limit exceeded
28	Execution timed out	2107 ms	939532 KB	Time limit exceeded
29	Execution timed out	2040 ms	938836 KB	Time limit exceeded
30	Execution timed out	2037 ms	927336 KB	Time limit exceeded
31	Correct	1808 ms	735396 KB	Output is correct
32	Execution timed out	2113 ms	850512 KB	Time limit exceeded