Submission #1062360

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1062360	2024-08-17T04:03:40 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	75.2083 / 100	2000 ms	76696 KB

tracks

#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());
			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});
					grid[temp->first][temp->second] = '.';
				}
			}
	}
}

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

18.3333333333 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	56 ms	2908 KB	Output isn't correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Incorrect	30 ms	3332 KB	Output isn't correct
5	Correct	5 ms	2652 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Incorrect	1 ms	2684 KB	Output isn't correct
9	Correct	1 ms	2652 KB	Output is correct
10	Correct	7 ms	2680 KB	Output is correct
11	Incorrect	7 ms	2652 KB	Output isn't correct
12	Incorrect	19 ms	2868 KB	Output isn't correct
13	Correct	5 ms	2648 KB	Output is correct
14	Correct	5 ms	2904 KB	Output is correct
15	Correct	41 ms	2652 KB	Output is correct
16	Incorrect	68 ms	3028 KB	Output isn't correct
17	Correct	25 ms	2648 KB	Output is correct
18	Incorrect	28 ms	3164 KB	Output isn't correct

Subtask #2

56.875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	15196 KB	Output is correct
2	Correct	128 ms	6856 KB	Output is correct
3	Correct	556 ms	15956 KB	Output is correct
4	Correct	143 ms	8784 KB	Output is correct
5	Correct	278 ms	12884 KB	Output is correct
6	Execution timed out	2035 ms	74776 KB	Time limit exceeded
7	Correct	4 ms	15964 KB	Output is correct
8	Correct	3 ms	15196 KB	Output is correct
9	Incorrect	8 ms	604 KB	Output isn't 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	129 ms	6744 KB	Output is correct
14	Correct	97 ms	4700 KB	Output is correct
15	Correct	24 ms	4708 KB	Output is correct
16	Correct	69 ms	2652 KB	Output is correct
17	Correct	333 ms	8796 KB	Output is correct
18	Correct	99 ms	8784 KB	Output is correct
19	Correct	128 ms	8788 KB	Output is correct
20	Correct	140 ms	9044 KB	Output is correct
21	Correct	333 ms	12896 KB	Output is correct
22	Correct	266 ms	13136 KB	Output is correct
23	Correct	664 ms	10836 KB	Output is correct
24	Correct	243 ms	13140 KB	Output is correct
25	Correct	412 ms	16236 KB	Output is correct
26	Correct	1397 ms	15120 KB	Output is correct
27	Correct	1988 ms	25548 KB	Output is correct
28	Execution timed out	2075 ms	76696 KB	Time limit exceeded
29	Execution timed out	2060 ms	65864 KB	Time limit exceeded
30	Execution timed out	2037 ms	58724 KB	Time limit exceeded
31	Execution timed out	2033 ms	17500 KB	Time limit exceeded
32	Correct	1835 ms	20556 KB	Output is correct