oj.uz

답안 #1062303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1062303 2024-08-17T02:46:57 Z danielzhu Tracks in the Snow (BOI13_tracks) C++17
86.875 / 100
 2000 ms 70736 KB 
#include <bits/stdc++.h>
using namespace std;
int H, W;
char grid[4001][4001];
vector<pair<int,int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void bfs(set<pair<int,int>> &from, set<pair<int,int>> &to, char cc){
	while(!from.empty()){
			auto temp = from.begin();
			from.erase(from.begin());
			grid[temp->first][temp->second] = '.';
			from.erase({temp->first, temp->second});
			int x = temp->first, y = temp->second;
			for(auto [dx, dy] : dir){
				if(x+dx > -1 && x+dx < H && y+dy > -1 && y+dy < W && grid[x+dx][y+dy] != '.'){
					if(grid[x+dx][y+dy] != cc) to.insert({x+dx, y+dy});
					else from.insert({x+dx, y+dy});
				}
			}
	}
}

int main(){
	cin>>H>>W;
	for(int i = 0; i < H; i++){
		string s; cin>>s;
		for(int j = 0; j < W; j++){
			grid[i][j] = s[j];
		}
	}
	int x = 0, y = 0, ans = 0;
	char cc = grid[0][0];
	set<pair<int,int>> F, R;
	if(cc == 'F') F.insert({0,0});
	else R.insert({0,0});
	while(true){
		if(cc == 'F' && F.empty()) break;
		if(cc == 'R' && R.empty()) break;
		if(cc == 'F')
			bfs(F, R, cc);
		else if(cc == 'R')
			bfs(R, F, cc);
		ans++;
		if(cc == 'F') cc = 'R';
		else if(cc == 'R') cc = 'F';
	}
	cout<<ans<<endl;
	return 0;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:31:6: warning: unused variable 'x' [-Wunused-variable]
   31 |  int x = 0, y = 0, ans = 0;
      |      ^
tracks.cpp:31:13: warning: unused variable 'y' [-Wunused-variable]
   31 |  int x = 0, y = 0, ans = 0;
      |             ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 2904 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 27 ms 3328 KB Output is correct
5 Correct 4 ms 2652 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 5 ms 2648 KB Output is correct
11 Correct 7 ms 2900 KB Output is correct
12 Correct 17 ms 2848 KB Output is correct
13 Correct 4 ms 2476 KB Output is correct
14 Correct 5 ms 2652 KB Output is correct
15 Correct 33 ms 2652 KB Output is correct
16 Correct 48 ms 2980 KB Output is correct
17 Correct 18 ms 2648 KB Output is correct
18 Correct 27 ms 3420 KB Output is correct

Subtask #2
56.875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 110 ms 6752 KB Output is correct
3 Correct 465 ms 15956 KB Output is correct
4 Correct 108 ms 8788 KB Output is correct
5 Correct 257 ms 12892 KB Output is correct
6 Execution timed out 2073 ms 69460 KB Time limit exceeded
7 Correct 3 ms 15960 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 5 ms 620 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 3 ms 15708 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct
13 Correct 104 ms 6764 KB Output is correct
14 Correct 60 ms 4700 KB Output is correct
15 Correct 24 ms 4700 KB Output is correct
16 Correct 58 ms 2740 KB Output is correct
17 Correct 264 ms 8804 KB Output is correct
18 Correct 93 ms 8784 KB Output is correct
19 Correct 132 ms 8788 KB Output is correct
20 Correct 104 ms 8788 KB Output is correct
21 Correct 261 ms 12880 KB Output is correct
22 Correct 262 ms 12880 KB Output is correct
23 Correct 525 ms 11052 KB Output is correct
24 Correct 225 ms 12888 KB Output is correct
25 Correct 372 ms 15972 KB Output is correct
26 Correct 1605 ms 15116 KB Output is correct
27 Execution timed out 2037 ms 25424 KB Time limit exceeded
28 Execution timed out 2029 ms 70736 KB Time limit exceeded
29 Execution timed out 2044 ms 63856 KB Time limit exceeded
30 Execution timed out 2058 ms 58728 KB Time limit exceeded
31 Execution timed out 2063 ms 17244 KB Time limit exceeded
32 Correct 1951 ms 20308 KB Output is correct