Submission #1063733

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063733	2024-08-18T00:31:28 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	91.25 / 100	2000 ms	1048576 KB

tracks

#include <bits/stdc++.h>
using namespace std;
int H, W;
int grid[4001][4001], cc[4001][4001];
queue<pair<int,int>> q;
vector<pair<int,int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 
void ff(int cur, int val){
	while(!q.empty()){
		auto temp = q.front();
		int x = temp.first, y = temp.second;
		q.pop();
		for(auto [dx, dy] : dir){
			if((x+dx > -1)&& (x+dx < H) && (y+dy > -1) && (y+dy < W) && (cc[x+dx][y+dy] == -1) && (grid[x+dx][y+dy] == cur)){
				cc[x+dx][y+dy] = val;
				q.push({x+dx, y+dy});
			}
		}
	}
}				
 
int main(){
	cin>>H>>W;
	memset(grid, 0, sizeof(grid));
	memset(cc, -1, sizeof(cc));
	for(int i = 0; i < H; i++){
		string s; cin>>s;
		for(int j = 0; j < W; j++){
			if(s[j] == 'F') grid[i][j] = 1;
			else if(s[j] == 'R') grid[i][j] = 2;
		}
	}
	int val = 0;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(cc[i][j] == -1 && grid[i][j] != 0){
				cc[i][j] = val;
				q.push({i,j});
				ff(grid[i][j], val);
				val++;
			}
		}
	}
	vector<unordered_set<int>> adj(val+1); 
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			if(grid[i][j] != 0){
				for(auto [dx, dy] : dir){
					if(i+dx > -1 && i+dx < H && j+dy > -1 && j+dy < W && cc[i+dx][j+dy] != cc[i][j] && cc[i+dx][j+dy] != -1){
						adj[cc[i][j]].insert(cc[i+dx][j+dy]);
						adj[cc[i+dx][j+dy]].insert(cc[i][j]);
					}
				}
			}
		}
	}
	queue<int> q1;
	q1.push(0);
	vector<int> d(val+1, -1);
	int ans = 0;
	d[0] = 0;
	while(!q1.empty()){
		auto temp = q1.front();
		q1.pop();
		for(auto i : adj[temp]){
			if(d[i] == -1){
				q1.push(i);
				d[i] = d[temp] + 1;
				ans = max(ans, d[i]);
			}
		}
	}
	cout<<ans+1<<endl;
	return 0;
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	82 ms	134740 KB	Output is correct
2	Correct	46 ms	125528 KB	Output is correct
3	Correct	46 ms	125572 KB	Output is correct
4	Correct	61 ms	126288 KB	Output is correct
5	Correct	62 ms	127572 KB	Output is correct
6	Correct	45 ms	125788 KB	Output is correct
7	Correct	45 ms	125764 KB	Output is correct
8	Correct	50 ms	125776 KB	Output is correct
9	Correct	47 ms	125776 KB	Output is correct
10	Correct	57 ms	127576 KB	Output is correct
11	Correct	53 ms	125780 KB	Output is correct
12	Correct	60 ms	129104 KB	Output is correct
13	Correct	51 ms	127568 KB	Output is correct
14	Correct	55 ms	127572 KB	Output is correct
15	Correct	95 ms	134744 KB	Output is correct
16	Correct	104 ms	134992 KB	Output is correct
17	Correct	74 ms	134224 KB	Output is correct
18	Correct	54 ms	126288 KB	Output is correct

Subtask #2

61.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	126804 KB	Output is correct
2	Correct	205 ms	173140 KB	Output is correct
3	Correct	919 ms	467236 KB	Output is correct
4	Correct	294 ms	185428 KB	Output is correct
5	Runtime error	1455 ms	1048576 KB	Execution killed with signal 9
6	Correct	1333 ms	258392 KB	Output is correct
7	Correct	53 ms	126544 KB	Output is correct
8	Correct	54 ms	126800 KB	Output is correct
9	Correct	60 ms	127056 KB	Output is correct
10	Correct	51 ms	126192 KB	Output is correct
11	Correct	54 ms	126108 KB	Output is correct
12	Correct	50 ms	128088 KB	Output is correct
13	Correct	183 ms	173016 KB	Output is correct
14	Correct	133 ms	153424 KB	Output is correct
15	Correct	170 ms	158544 KB	Output is correct
16	Correct	118 ms	147536 KB	Output is correct
17	Correct	429 ms	249340 KB	Output is correct
18	Correct	507 ms	252756 KB	Output is correct
19	Correct	284 ms	185296 KB	Output is correct
20	Correct	244 ms	203288 KB	Output is correct
21	Correct	606 ms	329812 KB	Output is correct
22	Runtime error	1228 ms	1048576 KB	Execution killed with signal 9
23	Correct	794 ms	364312 KB	Output is correct
24	Correct	906 ms	471272 KB	Output is correct
25	Execution timed out	2021 ms	651524 KB	Time limit exceeded
26	Correct	549 ms	125524 KB	Output is correct
27	Correct	678 ms	129576 KB	Output is correct
28	Correct	1397 ms	258468 KB	Output is correct
29	Correct	1105 ms	205072 KB	Output is correct
30	Correct	967 ms	181912 KB	Output is correct
31	Execution timed out	2064 ms	506140 KB	Time limit exceeded
32	Correct	684 ms	157396 KB	Output is correct