Submission #1062361

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1062361	2024-08-17T04:04:53 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	75.2083 / 100	2000 ms	76672 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	48 ms	2904 KB	Output isn't correct
2	Correct	1 ms	344 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Incorrect	26 ms	3424 KB	Output isn't correct
5	Correct	4 ms	2652 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	2652 KB	Output is correct
8	Incorrect	1 ms	2652 KB	Output isn't correct
9	Correct	1 ms	2652 KB	Output is correct
10	Correct	5 ms	2652 KB	Output is correct
11	Incorrect	6 ms	2908 KB	Output isn't correct
12	Incorrect	18 ms	2872 KB	Output isn't correct
13	Correct	4 ms	2652 KB	Output is correct
14	Correct	4 ms	2652 KB	Output is correct
15	Correct	42 ms	2804 KB	Output is correct
16	Incorrect	53 ms	2908 KB	Output isn't correct
17	Correct	27 ms	2652 KB	Output is correct
18	Incorrect	26 ms	3420 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	119 ms	6852 KB	Output is correct
3	Correct	538 ms	16124 KB	Output is correct
4	Correct	116 ms	8788 KB	Output is correct
5	Correct	249 ms	12880 KB	Output is correct
6	Execution timed out	2020 ms	76648 KB	Time limit exceeded
7	Correct	3 ms	15960 KB	Output is correct
8	Correct	3 ms	15196 KB	Output is correct
9	Incorrect	5 ms	500 KB	Output isn't correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	4 ms	15744 KB	Output is correct
12	Correct	1 ms	2652 KB	Output is correct
13	Correct	111 ms	6748 KB	Output is correct
14	Correct	64 ms	5016 KB	Output is correct
15	Correct	23 ms	4700 KB	Output is correct
16	Correct	61 ms	2652 KB	Output is correct
17	Correct	288 ms	8808 KB	Output is correct
18	Correct	90 ms	8788 KB	Output is correct
19	Correct	114 ms	8804 KB	Output is correct
20	Correct	155 ms	8796 KB	Output is correct
21	Correct	321 ms	12900 KB	Output is correct
22	Correct	234 ms	12884 KB	Output is correct
23	Correct	562 ms	10836 KB	Output is correct
24	Correct	217 ms	12884 KB	Output is correct
25	Correct	368 ms	15968 KB	Output is correct
26	Correct	1016 ms	15192 KB	Output is correct
27	Correct	1592 ms	25528 KB	Output is correct
28	Execution timed out	2072 ms	76672 KB	Time limit exceeded
29	Execution timed out	2048 ms	66444 KB	Time limit exceeded
30	Execution timed out	2053 ms	58608 KB	Time limit exceeded
31	Execution timed out	2068 ms	17556 KB	Time limit exceeded
32	Correct	1432 ms	20492 KB	Output is correct