oj.uz

답안 #876637

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876637 2023-11-22T06:29:45 Z vjudge1 Tracks in the Snow (BOI13_tracks) C++17
86.875 / 100
 2000 ms 943076 KB 
#include <iostream>
#include <vector>
#include <queue>

#define endl '\n'
#define pb emplace_back
#define push emplace

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].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

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 385024 KB Output is correct
2 Correct 179 ms 376660 KB Output is correct
3 Correct 158 ms 378784 KB Output is correct
4 Correct 114 ms 382160 KB Output is correct
5 Correct 90 ms 377412 KB Output is correct
6 Correct 86 ms 376656 KB Output is correct
7 Correct 85 ms 376736 KB Output is correct
8 Correct 86 ms 376736 KB Output is correct
9 Correct 85 ms 378808 KB Output is correct
10 Correct 83 ms 379760 KB Output is correct
11 Correct 85 ms 379984 KB Output is correct
12 Correct 91 ms 381520 KB Output is correct
13 Correct 84 ms 379472 KB Output is correct
14 Correct 85 ms 379732 KB Output is correct
15 Correct 105 ms 385104 KB Output is correct
16 Correct 115 ms 386644 KB Output is correct
17 Correct 102 ms 382804 KB Output is correct
18 Correct 101 ms 383936 KB Output is correct

Subtask #2
56.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 379220 KB Output is correct
2 Correct 196 ms 405844 KB Output is correct
3 Correct 566 ms 557396 KB Output is correct
4 Correct 212 ms 410804 KB Output is correct
5 Correct 526 ms 551120 KB Output is correct
6 Execution timed out 2100 ms 938560 KB Time limit exceeded
7 Correct 89 ms 379004 KB Output is correct
8 Correct 83 ms 379216 KB Output is correct
9 Correct 85 ms 379624 KB Output is correct
10 Correct 82 ms 378960 KB Output is correct
11 Correct 85 ms 379272 KB Output is correct
12 Correct 83 ms 379148 KB Output is correct
13 Correct 182 ms 405848 KB Output is correct
14 Correct 140 ms 393300 KB Output is correct
15 Correct 134 ms 392784 KB Output is correct
16 Correct 132 ms 391680 KB Output is correct
17 Correct 336 ms 446464 KB Output is correct
18 Correct 308 ms 429464 KB Output is correct
19 Correct 210 ms 411876 KB Output is correct
20 Correct 196 ms 420796 KB Output is correct
21 Correct 362 ms 484996 KB Output is correct
22 Correct 506 ms 553744 KB Output is correct
23 Correct 612 ms 511144 KB Output is correct
24 Correct 404 ms 506884 KB Output is correct
25 Correct 1555 ms 580640 KB Output is correct
26 Correct 1994 ms 809572 KB Output is correct
27 Execution timed out 2051 ms 940228 KB Time limit exceeded
28 Execution timed out 2053 ms 942568 KB Time limit exceeded
29 Execution timed out 2040 ms 943076 KB Time limit exceeded
30 Execution timed out 2063 ms 931408 KB Time limit exceeded
31 Correct 1825 ms 738144 KB Output is correct
32 Execution timed out 2033 ms 854896 KB Time limit exceeded