Submission #1063704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063704	2024-08-18T00:00:11 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	2000 ms	793880 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 && grid[i+dx][j+dy] != grid[i][j] && grid[i+dx][j+dy] != 0){
						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> v(val+1, 0), d(val+1, 0);
	v[0] = 1;
	int ans = 0;
	while(!q1.empty()){
		auto temp = q1.front();
		q1.pop();
		for(auto i : adj[temp]){
			if(!v[i]){
				q1.push(i);
				v[i] = 1;
				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	93 ms	132696 KB	Output is correct
2	Correct	45 ms	125520 KB	Output is correct
3	Correct	46 ms	125524 KB	Output is correct
4	Correct	63 ms	126036 KB	Output is correct
5	Correct	51 ms	126952 KB	Output is correct
6	Correct	45 ms	125612 KB	Output is correct
7	Correct	45 ms	125772 KB	Output is correct
8	Correct	48 ms	125524 KB	Output is correct
9	Correct	46 ms	125724 KB	Output is correct
10	Correct	51 ms	126804 KB	Output is correct
11	Correct	49 ms	125776 KB	Output is correct
12	Correct	65 ms	128048 KB	Output is correct
13	Correct	50 ms	126800 KB	Output is correct
14	Correct	51 ms	126800 KB	Output is correct
15	Correct	79 ms	132176 KB	Output is correct
16	Correct	94 ms	132692 KB	Output is correct
17	Correct	79 ms	131664 KB	Output is correct
18	Correct	61 ms	126032 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	48 ms	126288 KB	Output is correct
2	Correct	167 ms	158228 KB	Output is correct
3	Correct	722 ms	353616 KB	Output is correct
4	Correct	227 ms	165712 KB	Output is correct
5	Correct	846 ms	793880 KB	Output is correct
6	Correct	1596 ms	209120 KB	Output is correct
7	Correct	57 ms	126288 KB	Output is correct
8	Correct	49 ms	126328 KB	Output is correct
9	Correct	50 ms	126764 KB	Output is correct
10	Correct	45 ms	126084 KB	Output is correct
11	Correct	51 ms	125920 KB	Output is correct
12	Correct	48 ms	127204 KB	Output is correct
13	Correct	170 ms	158292 KB	Output is correct
14	Correct	110 ms	144724 KB	Output is correct
15	Correct	110 ms	146768 KB	Output is correct
16	Correct	104 ms	141140 KB	Output is correct
17	Correct	350 ms	210512 KB	Output is correct
18	Correct	333 ms	207568 KB	Output is correct
19	Correct	224 ms	165716 KB	Output is correct
20	Correct	197 ms	177556 KB	Output is correct
21	Correct	455 ms	261972 KB	Output is correct
22	Correct	803 ms	793788 KB	Output is correct
23	Correct	655 ms	289548 KB	Output is correct
24	Correct	461 ms	348244 KB	Output is correct
25	Correct	1333 ms	464424 KB	Output is correct
26	Correct	465 ms	131668 KB	Output is correct
27	Correct	704 ms	136236 KB	Output is correct
28	Correct	1631 ms	217380 KB	Output is correct
29	Correct	1501 ms	183104 KB	Output is correct
30	Correct	1193 ms	168532 KB	Output is correct
31	Execution timed out	2049 ms	421904 KB	Time limit exceeded
32	Correct	671 ms	154196 KB	Output is correct