Submission #1062362

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1062362	2024-08-17T04:06:28 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	93.4375 / 100	2000 ms	73556 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[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});
	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

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	2904 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2652 KB	Output is correct
4	Correct	18 ms	3204 KB	Output is correct
5	Correct	5 ms	2648 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	4 ms	2676 KB	Output is correct
11	Correct	5 ms	2912 KB	Output is correct
12	Correct	10 ms	2652 KB	Output is correct
13	Correct	4 ms	2652 KB	Output is correct
14	Correct	3 ms	2676 KB	Output is correct
15	Correct	26 ms	2792 KB	Output is correct
16	Correct	29 ms	2984 KB	Output is correct
17	Correct	14 ms	2652 KB	Output is correct
18	Correct	19 ms	3260 KB	Output is correct

Subtask #2

63.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	15192 KB	Output is correct
2	Correct	82 ms	6756 KB	Output is correct
3	Correct	382 ms	15952 KB	Output is correct
4	Correct	92 ms	8788 KB	Output is correct
5	Correct	246 ms	12884 KB	Output is correct
6	Execution timed out	2049 ms	73556 KB	Time limit exceeded
7	Correct	3 ms	15964 KB	Output is correct
8	Correct	3 ms	15196 KB	Output is correct
9	Correct	3 ms	604 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	73 ms	6840 KB	Output is correct
14	Correct	43 ms	4764 KB	Output is correct
15	Correct	22 ms	4700 KB	Output is correct
16	Correct	38 ms	2648 KB	Output is correct
17	Correct	189 ms	8940 KB	Output is correct
18	Correct	86 ms	8784 KB	Output is correct
19	Correct	99 ms	8800 KB	Output is correct
20	Correct	88 ms	8784 KB	Output is correct
21	Correct	226 ms	12896 KB	Output is correct
22	Correct	228 ms	12880 KB	Output is correct
23	Correct	381 ms	11060 KB	Output is correct
24	Correct	208 ms	12884 KB	Output is correct
25	Correct	388 ms	15972 KB	Output is correct
26	Correct	1002 ms	15188 KB	Output is correct
27	Correct	1510 ms	25428 KB	Output is correct
28	Execution timed out	2043 ms	73552 KB	Time limit exceeded
29	Execution timed out	2076 ms	64848 KB	Time limit exceeded
30	Correct	1934 ms	58704 KB	Output is correct
31	Correct	1345 ms	17492 KB	Output is correct
32	Correct	1321 ms	20564 KB	Output is correct