Submission #1063721

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063721	2024-08-18T00:14:39 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	97.8125 / 100	2000 ms	800596 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	97 ms	132692 KB	Output is correct
2	Correct	46 ms	125720 KB	Output is correct
3	Correct	53 ms	125684 KB	Output is correct
4	Correct	65 ms	126032 KB	Output is correct
5	Correct	52 ms	126924 KB	Output is correct
6	Correct	48 ms	125572 KB	Output is correct
7	Correct	51 ms	125776 KB	Output is correct
8	Correct	67 ms	125520 KB	Output is correct
9	Correct	47 ms	125692 KB	Output is correct
10	Correct	48 ms	126804 KB	Output is correct
11	Correct	48 ms	125776 KB	Output is correct
12	Correct	71 ms	128272 KB	Output is correct
13	Correct	52 ms	126804 KB	Output is correct
14	Correct	53 ms	126800 KB	Output is correct
15	Correct	81 ms	132180 KB	Output is correct
16	Correct	91 ms	132688 KB	Output is correct
17	Correct	70 ms	131720 KB	Output is correct
18	Correct	67 ms	126032 KB	Output is correct

Subtask #2

67.8125 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	126284 KB	Output is correct
2	Correct	171 ms	158324 KB	Output is correct
3	Correct	740 ms	353620 KB	Output is correct
4	Correct	221 ms	165716 KB	Output is correct
5	Correct	828 ms	800596 KB	Output is correct
6	Correct	1685 ms	209188 KB	Output is correct
7	Correct	52 ms	126292 KB	Output is correct
8	Correct	50 ms	126416 KB	Output is correct
9	Correct	57 ms	126800 KB	Output is correct
10	Correct	50 ms	126036 KB	Output is correct
11	Correct	47 ms	126016 KB	Output is correct
12	Correct	47 ms	127316 KB	Output is correct
13	Correct	170 ms	158276 KB	Output is correct
14	Correct	121 ms	144724 KB	Output is correct
15	Correct	122 ms	146712 KB	Output is correct
16	Correct	107 ms	141084 KB	Output is correct
17	Correct	373 ms	210596 KB	Output is correct
18	Correct	352 ms	207444 KB	Output is correct
19	Correct	219 ms	165756 KB	Output is correct
20	Correct	197 ms	177636 KB	Output is correct
21	Correct	446 ms	261968 KB	Output is correct
22	Correct	833 ms	800592 KB	Output is correct
23	Correct	649 ms	289588 KB	Output is correct
24	Correct	462 ms	348124 KB	Output is correct
25	Correct	1389 ms	464348 KB	Output is correct
26	Correct	439 ms	125536 KB	Output is correct
27	Correct	710 ms	128084 KB	Output is correct
28	Correct	1606 ms	209232 KB	Output is correct
29	Correct	1473 ms	174928 KB	Output is correct
30	Correct	1193 ms	160680 KB	Output is correct
31	Execution timed out	2059 ms	416536 KB	Time limit exceeded
32	Correct	636 ms	146212 KB	Output is correct