Submission #1063720

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063720	2024-08-18T00:14:13 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	95.625 / 100	1957 ms	1048576 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<unordered_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	79 ms	134992 KB	Output is correct
2	Correct	45 ms	125524 KB	Output is correct
3	Correct	45 ms	125780 KB	Output is correct
4	Correct	59 ms	126292 KB	Output is correct
5	Correct	52 ms	127572 KB	Output is correct
6	Correct	44 ms	125512 KB	Output is correct
7	Correct	44 ms	125780 KB	Output is correct
8	Correct	47 ms	125780 KB	Output is correct
9	Correct	50 ms	125788 KB	Output is correct
10	Correct	51 ms	127568 KB	Output is correct
11	Correct	51 ms	125856 KB	Output is correct
12	Correct	60 ms	129120 KB	Output is correct
13	Correct	61 ms	127508 KB	Output is correct
14	Correct	56 ms	127572 KB	Output is correct
15	Correct	77 ms	134932 KB	Output is correct
16	Correct	89 ms	134992 KB	Output is correct
17	Correct	71 ms	134224 KB	Output is correct
18	Correct	54 ms	126288 KB	Output is correct

Subtask #2

65.625 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	126804 KB	Output is correct
2	Correct	196 ms	173956 KB	Output is correct
3	Correct	802 ms	472916 KB	Output is correct
4	Correct	253 ms	186192 KB	Output is correct
5	Runtime error	1441 ms	1048576 KB	Execution killed with signal 9
6	Correct	1277 ms	260476 KB	Output is correct
7	Correct	49 ms	126552 KB	Output is correct
8	Correct	54 ms	126800 KB	Output is correct
9	Correct	53 ms	127272 KB	Output is correct
10	Correct	47 ms	126288 KB	Output is correct
11	Correct	50 ms	126036 KB	Output is correct
12	Correct	54 ms	128084 KB	Output is correct
13	Correct	170 ms	173848 KB	Output is correct
14	Correct	118 ms	153944 KB	Output is correct
15	Correct	139 ms	159180 KB	Output is correct
16	Correct	108 ms	148048 KB	Output is correct
17	Correct	356 ms	251476 KB	Output is correct
18	Correct	442 ms	255056 KB	Output is correct
19	Correct	259 ms	186196 KB	Output is correct
20	Correct	260 ms	204532 KB	Output is correct
21	Correct	638 ms	333136 KB	Output is correct
22	Runtime error	916 ms	1048576 KB	Execution killed with signal 9
23	Correct	678 ms	368212 KB	Output is correct
24	Correct	805 ms	477016 KB	Output is correct
25	Correct	1853 ms	660564 KB	Output is correct
26	Correct	528 ms	125524 KB	Output is correct
27	Correct	696 ms	129616 KB	Output is correct
28	Correct	1331 ms	260476 KB	Output is correct
29	Correct	1148 ms	206320 KB	Output is correct
30	Correct	962 ms	182728 KB	Output is correct
31	Correct	1957 ms	511272 KB	Output is correct
32	Correct	704 ms	157868 KB	Output is correct