oj.uz

Submission #1063688

# Submission time Handle Problem Language Result Execution time Memory
1063688 2024-08-17T23:31:01 Z danielzhu Tracks in the Snow (BOI13_tracks) C++17
95.625 / 100
 2000 ms 802640 KB 
#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 i, int j, int cur, int val){
	q.push({i, j});
	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;
		}
	}
	//cout<<cc[1][1]<<" "<<grid[1][1]<<endl;
	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;
				ff(i, j, grid[i][j], val);
				val++;
			}
		}
	}
	/*for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
		    cout<<cc[i][j];
		}
		cout<<endl;
	}*/
	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 94 ms 132944 KB Output is correct
2 Correct 46 ms 125524 KB Output is correct
3 Correct 54 ms 125780 KB Output is correct
4 Correct 57 ms 126284 KB Output is correct
5 Correct 56 ms 127000 KB Output is correct
6 Correct 51 ms 125624 KB Output is correct
7 Correct 47 ms 126032 KB Output is correct
8 Correct 46 ms 125524 KB Output is correct
9 Correct 46 ms 125776 KB Output is correct
10 Correct 50 ms 127060 KB Output is correct
11 Correct 50 ms 125776 KB Output is correct
12 Correct 63 ms 128360 KB Output is correct
13 Correct 54 ms 126980 KB Output is correct
14 Correct 52 ms 127056 KB Output is correct
15 Correct 77 ms 132436 KB Output is correct
16 Correct 92 ms 132944 KB Output is correct
17 Correct 71 ms 131916 KB Output is correct
18 Correct 61 ms 126288 KB Output is correct

Subtask #2
65.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 126548 KB Output is correct
2 Correct 184 ms 159828 KB Output is correct
3 Correct 724 ms 369288 KB Output is correct
4 Correct 220 ms 169300 KB Output is correct
5 Correct 827 ms 802576 KB Output is correct
6 Correct 1677 ms 225072 KB Output is correct
7 Correct 48 ms 126292 KB Output is correct
8 Correct 49 ms 126548 KB Output is correct
9 Correct 55 ms 126804 KB Output is correct
10 Correct 50 ms 126032 KB Output is correct
11 Correct 52 ms 126032 KB Output is correct
12 Correct 47 ms 127324 KB Output is correct
13 Correct 175 ms 159820 KB Output is correct
14 Correct 127 ms 145488 KB Output is correct
15 Correct 117 ms 147708 KB Output is correct
16 Correct 112 ms 141652 KB Output is correct
17 Correct 352 ms 214420 KB Output is correct
18 Correct 319 ms 211540 KB Output is correct
19 Correct 208 ms 169264 KB Output is correct
20 Correct 217 ms 180964 KB Output is correct
21 Correct 454 ms 270956 KB Output is correct
22 Correct 826 ms 802640 KB Output is correct
23 Correct 660 ms 297296 KB Output is correct
24 Correct 477 ms 357092 KB Output is correct
25 Correct 1338 ms 480116 KB Output is correct
26 Incorrect 536 ms 137560 KB Output isn't correct
27 Correct 703 ms 143700 KB Output is correct
28 Correct 1644 ms 224848 KB Output is correct
29 Correct 1443 ms 190512 KB Output is correct
30 Correct 1168 ms 175800 KB Output is correct
31 Execution timed out 2094 ms 426324 KB Time limit exceeded
32 Correct 673 ms 161660 KB Output is correct