Submission #1063728

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063728	2024-08-18T00:24:29 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	93.4375 / 100	2000 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 && 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	80 ms	134992 KB	Output is correct
2	Correct	45 ms	125520 KB	Output is correct
3	Correct	44 ms	125780 KB	Output is correct
4	Correct	57 ms	126316 KB	Output is correct
5	Correct	58 ms	127576 KB	Output is correct
6	Correct	45 ms	125520 KB	Output is correct
7	Correct	45 ms	125780 KB	Output is correct
8	Correct	51 ms	125776 KB	Output is correct
9	Correct	45 ms	125800 KB	Output is correct
10	Correct	51 ms	127572 KB	Output is correct
11	Correct	49 ms	125776 KB	Output is correct
12	Correct	60 ms	128968 KB	Output is correct
13	Correct	52 ms	127496 KB	Output is correct
14	Correct	57 ms	127568 KB	Output is correct
15	Correct	81 ms	135000 KB	Output is correct
16	Correct	95 ms	134992 KB	Output is correct
17	Correct	74 ms	134224 KB	Output is correct
18	Correct	54 ms	126292 KB	Output is correct

Subtask #2

63.4375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	126804 KB	Output is correct
2	Correct	172 ms	173908 KB	Output is correct
3	Correct	779 ms	472916 KB	Output is correct
4	Correct	234 ms	186312 KB	Output is correct
5	Runtime error	865 ms	1048576 KB	Execution killed with signal 9
6	Correct	1216 ms	260432 KB	Output is correct
7	Correct	49 ms	126548 KB	Output is correct
8	Correct	48 ms	126796 KB	Output is correct
9	Correct	54 ms	127104 KB	Output is correct
10	Correct	47 ms	126288 KB	Output is correct
11	Correct	47 ms	126188 KB	Output is correct
12	Correct	47 ms	128288 KB	Output is correct
13	Correct	193 ms	173864 KB	Output is correct
14	Correct	116 ms	153684 KB	Output is correct
15	Correct	131 ms	159188 KB	Output is correct
16	Correct	116 ms	148052 KB	Output is correct
17	Correct	346 ms	251528 KB	Output is correct
18	Correct	409 ms	255000 KB	Output is correct
19	Correct	229 ms	186448 KB	Output is correct
20	Correct	261 ms	204512 KB	Output is correct
21	Correct	598 ms	332996 KB	Output is correct
22	Runtime error	1465 ms	1048576 KB	Execution killed with signal 9
23	Correct	669 ms	368156 KB	Output is correct
24	Correct	576 ms	477092 KB	Output is correct
25	Correct	1827 ms	660464 KB	Output is correct
26	Correct	516 ms	125724 KB	Output is correct
27	Correct	639 ms	129628 KB	Output is correct
28	Correct	1230 ms	260476 KB	Output is correct
29	Correct	1096 ms	206324 KB	Output is correct
30	Correct	960 ms	182724 KB	Output is correct
31	Execution timed out	2054 ms	511256 KB	Time limit exceeded
32	Correct	692 ms	158084 KB	Output is correct