Submission #1063703

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063703	2024-08-17T23:55:27 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	95.625 / 100	2000 ms	793872 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 = INT_MIN;
	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	132688 KB	Output is correct
2	Correct	45 ms	125520 KB	Output is correct
3	Correct	47 ms	125776 KB	Output is correct
4	Correct	57 ms	126032 KB	Output is correct
5	Correct	52 ms	126996 KB	Output is correct
6	Correct	47 ms	125676 KB	Output is correct
7	Correct	49 ms	125776 KB	Output is correct
8	Correct	48 ms	125524 KB	Output is correct
9	Correct	45 ms	125780 KB	Output is correct
10	Correct	48 ms	126936 KB	Output is correct
11	Correct	47 ms	125776 KB	Output is correct
12	Correct	63 ms	128124 KB	Output is correct
13	Correct	49 ms	126996 KB	Output is correct
14	Correct	51 ms	126808 KB	Output is correct
15	Correct	77 ms	132180 KB	Output is correct
16	Correct	89 ms	132520 KB	Output is correct
17	Correct	71 ms	131748 KB	Output is correct
18	Correct	58 ms	126032 KB	Output is correct

Subtask #2

65.625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	126388 KB	Output is correct
2	Correct	164 ms	158292 KB	Output is correct
3	Correct	733 ms	353572 KB	Output is correct
4	Correct	213 ms	165676 KB	Output is correct
5	Correct	847 ms	793872 KB	Output is correct
6	Correct	1592 ms	209188 KB	Output is correct
7	Correct	46 ms	126168 KB	Output is correct
8	Correct	50 ms	126292 KB	Output is correct
9	Correct	49 ms	126800 KB	Output is correct
10	Correct	48 ms	126032 KB	Output is correct
11	Correct	49 ms	126036 KB	Output is correct
12	Correct	47 ms	127312 KB	Output is correct
13	Correct	187 ms	158436 KB	Output is correct
14	Correct	114 ms	144720 KB	Output is correct
15	Correct	108 ms	146768 KB	Output is correct
16	Correct	102 ms	141136 KB	Output is correct
17	Correct	355 ms	210512 KB	Output is correct
18	Correct	328 ms	207444 KB	Output is correct
19	Correct	207 ms	165624 KB	Output is correct
20	Correct	206 ms	177696 KB	Output is correct
21	Correct	436 ms	261972 KB	Output is correct
22	Correct	825 ms	793752 KB	Output is correct
23	Correct	680 ms	289564 KB	Output is correct
24	Correct	459 ms	348244 KB	Output is correct
25	Correct	1301 ms	464496 KB	Output is correct
26	Incorrect	462 ms	125732 KB	Output isn't correct
27	Correct	690 ms	128080 KB	Output is correct
28	Correct	1695 ms	209232 KB	Output is correct
29	Correct	1448 ms	174928 KB	Output is correct
30	Correct	1197 ms	161012 KB	Output is correct
31	Execution timed out	2060 ms	403284 KB	Time limit exceeded
32	Correct	651 ms	146212 KB	Output is correct