Submission #1063732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063732	2024-08-18T00:30:24 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	2000 ms	781020 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<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	97 ms	132700 KB	Output is correct
2	Correct	47 ms	125524 KB	Output is correct
3	Correct	52 ms	125780 KB	Output is correct
4	Correct	64 ms	126288 KB	Output is correct
5	Correct	54 ms	127060 KB	Output is correct
6	Correct	48 ms	125748 KB	Output is correct
7	Correct	53 ms	125524 KB	Output is correct
8	Correct	48 ms	125564 KB	Output is correct
9	Correct	48 ms	125772 KB	Output is correct
10	Correct	54 ms	127032 KB	Output is correct
11	Correct	49 ms	125668 KB	Output is correct
12	Correct	65 ms	128340 KB	Output is correct
13	Correct	53 ms	126844 KB	Output is correct
14	Correct	54 ms	127060 KB	Output is correct
15	Correct	106 ms	132232 KB	Output is correct
16	Correct	99 ms	132688 KB	Output is correct
17	Correct	79 ms	131900 KB	Output is correct
18	Correct	59 ms	126204 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	126388 KB	Output is correct
2	Correct	178 ms	158492 KB	Output is correct
3	Correct	743 ms	356312 KB	Output is correct
4	Correct	236 ms	167248 KB	Output is correct
5	Correct	841 ms	781020 KB	Output is correct
6	Correct	1604 ms	215336 KB	Output is correct
7	Correct	55 ms	126288 KB	Output is correct
8	Correct	51 ms	126396 KB	Output is correct
9	Correct	50 ms	126800 KB	Output is correct
10	Correct	49 ms	126032 KB	Output is correct
11	Correct	49 ms	126044 KB	Output is correct
12	Correct	49 ms	127252 KB	Output is correct
13	Correct	175 ms	157780 KB	Output is correct
14	Correct	145 ms	144332 KB	Output is correct
15	Correct	114 ms	146256 KB	Output is correct
16	Correct	105 ms	140828 KB	Output is correct
17	Correct	364 ms	208464 KB	Output is correct
18	Correct	330 ms	205392 KB	Output is correct
19	Correct	216 ms	164892 KB	Output is correct
20	Correct	225 ms	176388 KB	Output is correct
21	Correct	503 ms	258588 KB	Output is correct
22	Correct	828 ms	776272 KB	Output is correct
23	Correct	666 ms	285724 KB	Output is correct
24	Correct	472 ms	342356 KB	Output is correct
25	Correct	1508 ms	455504 KB	Output is correct
26	Correct	579 ms	125748 KB	Output is correct
27	Correct	724 ms	128080 KB	Output is correct
28	Correct	1666 ms	206896 KB	Output is correct
29	Correct	1490 ms	173648 KB	Output is correct
30	Correct	1191 ms	159840 KB	Output is correct
31	Execution timed out	2089 ms	411124 KB	Time limit exceeded
32	Correct	695 ms	145488 KB	Output is correct