Submission #1063701

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063701	2024-08-17T23:47:21 Z	danielzhu	Tracks in the Snow (BOI13_tracks)	C++17	95.625 / 100	2000 ms	793804 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	89 ms	132640 KB	Output is correct
2	Correct	48 ms	125520 KB	Output is correct
3	Correct	47 ms	125776 KB	Output is correct
4	Correct	59 ms	126036 KB	Output is correct
5	Correct	57 ms	127012 KB	Output is correct
6	Correct	44 ms	125532 KB	Output is correct
7	Correct	52 ms	125524 KB	Output is correct
8	Correct	48 ms	125576 KB	Output is correct
9	Correct	46 ms	125780 KB	Output is correct
10	Correct	52 ms	126800 KB	Output is correct
11	Correct	51 ms	125812 KB	Output is correct
12	Correct	67 ms	128084 KB	Output is correct
13	Correct	48 ms	126808 KB	Output is correct
14	Correct	52 ms	126800 KB	Output is correct
15	Correct	82 ms	132220 KB	Output is correct
16	Correct	92 ms	132692 KB	Output is correct
17	Correct	72 ms	131808 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	51 ms	126292 KB	Output is correct
2	Correct	177 ms	158292 KB	Output is correct
3	Correct	733 ms	353616 KB	Output is correct
4	Correct	224 ms	165712 KB	Output is correct
5	Correct	831 ms	793804 KB	Output is correct
6	Correct	1682 ms	209232 KB	Output is correct
7	Correct	48 ms	126292 KB	Output is correct
8	Correct	51 ms	126292 KB	Output is correct
9	Correct	54 ms	126688 KB	Output is correct
10	Correct	45 ms	125968 KB	Output is correct
11	Correct	46 ms	126028 KB	Output is correct
12	Correct	54 ms	127140 KB	Output is correct
13	Correct	174 ms	158288 KB	Output is correct
14	Correct	124 ms	144664 KB	Output is correct
15	Correct	112 ms	146740 KB	Output is correct
16	Correct	129 ms	141140 KB	Output is correct
17	Correct	372 ms	210512 KB	Output is correct
18	Correct	360 ms	207444 KB	Output is correct
19	Correct	236 ms	165660 KB	Output is correct
20	Correct	206 ms	177708 KB	Output is correct
21	Correct	455 ms	261968 KB	Output is correct
22	Correct	812 ms	793804 KB	Output is correct
23	Correct	680 ms	289620 KB	Output is correct
24	Correct	480 ms	348244 KB	Output is correct
25	Correct	1388 ms	464464 KB	Output is correct
26	Incorrect	534 ms	125724 KB	Output isn't correct
27	Correct	698 ms	128084 KB	Output is correct
28	Correct	1757 ms	209144 KB	Output is correct
29	Correct	1526 ms	174924 KB	Output is correct
30	Correct	1335 ms	160596 KB	Output is correct
31	Execution timed out	2080 ms	416540 KB	Time limit exceeded
32	Correct	675 ms	146256 KB	Output is correct