Submission #1063702

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063702	2024-08-17T23:52:38 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	91.25 / 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 && 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	91 ms	135024 KB	Output is correct
2	Correct	51 ms	125524 KB	Output is correct
3	Correct	49 ms	125780 KB	Output is correct
4	Correct	59 ms	126248 KB	Output is correct
5	Correct	50 ms	127572 KB	Output is correct
6	Correct	49 ms	125512 KB	Output is correct
7	Correct	46 ms	125780 KB	Output is correct
8	Correct	44 ms	125780 KB	Output is correct
9	Correct	44 ms	125776 KB	Output is correct
10	Correct	49 ms	127568 KB	Output is correct
11	Correct	55 ms	125780 KB	Output is correct
12	Correct	59 ms	129040 KB	Output is correct
13	Correct	53 ms	127604 KB	Output is correct
14	Correct	50 ms	127572 KB	Output is correct
15	Correct	79 ms	134992 KB	Output is correct
16	Correct	93 ms	135080 KB	Output is correct
17	Correct	74 ms	134228 KB	Output is correct
18	Correct	53 ms	126288 KB	Output is correct

Subtask #2

61.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	126800 KB	Output is correct
2	Correct	168 ms	173920 KB	Output is correct
3	Correct	826 ms	472916 KB	Output is correct
4	Correct	308 ms	186192 KB	Output is correct
5	Runtime error	1516 ms	1048576 KB	Execution killed with signal 9
6	Correct	1256 ms	260476 KB	Output is correct
7	Correct	49 ms	126548 KB	Output is correct
8	Correct	51 ms	126872 KB	Output is correct
9	Correct	55 ms	127316 KB	Output is correct
10	Correct	55 ms	126340 KB	Output is correct
11	Correct	52 ms	126036 KB	Output is correct
12	Correct	48 ms	128252 KB	Output is correct
13	Correct	197 ms	173904 KB	Output is correct
14	Correct	152 ms	153680 KB	Output is correct
15	Correct	157 ms	159060 KB	Output is correct
16	Correct	114 ms	148048 KB	Output is correct
17	Correct	378 ms	251476 KB	Output is correct
18	Correct	523 ms	254976 KB	Output is correct
19	Correct	232 ms	186452 KB	Output is correct
20	Correct	298 ms	204672 KB	Output is correct
21	Correct	501 ms	333136 KB	Output is correct
22	Runtime error	959 ms	1048576 KB	Execution killed with signal 9
23	Correct	669 ms	368208 KB	Output is correct
24	Correct	596 ms	477008 KB	Output is correct
25	Correct	1824 ms	660560 KB	Output is correct
26	Incorrect	510 ms	125744 KB	Output isn't correct
27	Correct	664 ms	129616 KB	Output is correct
28	Correct	1334 ms	260436 KB	Output is correct
29	Correct	1073 ms	206272 KB	Output is correct
30	Correct	915 ms	182724 KB	Output is correct
31	Execution timed out	2045 ms	511312 KB	Time limit exceeded
32	Correct	647 ms	157868 KB	Output is correct