Submission #1063727

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063727	2024-08-18T00:23:35 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	2000 ms	793928 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> 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	102 ms	132692 KB	Output is correct
2	Correct	45 ms	125532 KB	Output is correct
3	Correct	45 ms	125524 KB	Output is correct
4	Correct	56 ms	126036 KB	Output is correct
5	Correct	48 ms	126804 KB	Output is correct
6	Correct	45 ms	125708 KB	Output is correct
7	Correct	50 ms	125776 KB	Output is correct
8	Correct	47 ms	125524 KB	Output is correct
9	Correct	53 ms	125784 KB	Output is correct
10	Correct	65 ms	126960 KB	Output is correct
11	Correct	48 ms	125668 KB	Output is correct
12	Correct	74 ms	128288 KB	Output is correct
13	Correct	49 ms	126800 KB	Output is correct
14	Correct	59 ms	126800 KB	Output is correct
15	Correct	77 ms	132176 KB	Output is correct
16	Correct	90 ms	132688 KB	Output is correct
17	Correct	66 ms	131664 KB	Output is correct
18	Correct	56 ms	126036 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	126288 KB	Output is correct
2	Correct	167 ms	158288 KB	Output is correct
3	Correct	729 ms	353488 KB	Output is correct
4	Correct	234 ms	165712 KB	Output is correct
5	Correct	819 ms	793928 KB	Output is correct
6	Correct	1583 ms	209232 KB	Output is correct
7	Correct	49 ms	126288 KB	Output is correct
8	Correct	51 ms	126288 KB	Output is correct
9	Correct	48 ms	126804 KB	Output is correct
10	Correct	50 ms	125996 KB	Output is correct
11	Correct	46 ms	126004 KB	Output is correct
12	Correct	46 ms	127156 KB	Output is correct
13	Correct	160 ms	158396 KB	Output is correct
14	Correct	110 ms	144720 KB	Output is correct
15	Correct	107 ms	146772 KB	Output is correct
16	Correct	104 ms	141136 KB	Output is correct
17	Correct	352 ms	210520 KB	Output is correct
18	Correct	347 ms	207532 KB	Output is correct
19	Correct	212 ms	165672 KB	Output is correct
20	Correct	195 ms	177744 KB	Output is correct
21	Correct	432 ms	261968 KB	Output is correct
22	Correct	888 ms	793888 KB	Output is correct
23	Correct	718 ms	289620 KB	Output is correct
24	Correct	479 ms	348244 KB	Output is correct
25	Correct	1372 ms	464468 KB	Output is correct
26	Correct	517 ms	125524 KB	Output is correct
27	Correct	685 ms	128084 KB	Output is correct
28	Correct	1596 ms	209232 KB	Output is correct
29	Correct	1518 ms	174932 KB	Output is correct
30	Correct	1240 ms	160552 KB	Output is correct
31	Execution timed out	2044 ms	416540 KB	Time limit exceeded
32	Correct	682 ms	146000 KB	Output is correct