Submission #989878

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
989878	2024-05-28T22:58:13 Z	vjudge1	Tracks in the Snow (BOI13_tracks)	C++17	70.9375 / 100	966 ms	227104 KB

tracks

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair<int,int> pii;



const int S = 4000;
char meadow[S][S];
int dist[S][S];
bool vis[S][S];
const int INF = 1e8;

void reset(){
	for(int i = 0; i < S; i++){
		for(int j = 0; j < S; j++){
			dist[i][j] = INF;
		}
	}
}
int solve(int h, int w){

	reset();
	int ans = 0;
	pii start = {0,0};
	deque<pii> dq;
	dq.push_back(start);
	dist[0][0] = 0;
	while(dq.size()){
		auto [a, b] = dq.front(); dq.pop_front();
		
		if(vis[a][b]) continue;
		vis[a][b] = true;
		char animal = meadow[a][b];
		// obtener vecinos
		vector<pii> vecinos;
		if (a > 0){
			if(!vis[a-1][b]){
				pii up = {a-1, b};
				char animal_up = meadow[up.ff][up.ss];
				if(animal_up != '.'){
					vecinos.pb(up);
				}
			}
		}
		if(a < h-1){
			if(!vis[a+1][b]){
				pii down = {a+1, b};
				char animal_down = meadow[down.ff][down.ss];
				if(animal_down != '.'){
					vecinos.pb(down);
				}
			}			
		}
		if(b > 0){
			if(!vis[a][b-1]){
				pii left = {a, b-1};
				char animal_left = meadow[left.ff][left.ss];
				if(animal_left != '.'){
					vecinos.pb(left);
				}
			}			
		}
		if(b < h-1){
			if(!vis[a][b+1]){
				pii right = {a, b+1};
				char animal_right = meadow[right.ff][right.ss];
				if(animal_right != '.'){
					vecinos.pb(right);
				}
			}
		}
		
		// iterar por vecinos
		for(auto [x,y]: vecinos){
			int d = 0;
			if(meadow[x][y] != animal){
				d = 1;
			}
			// if (dist[curr_node] + d > dist[to]) continue;
			if(dist[a][b] + d > dist[x][y]) continue;
			
			dist[x][y] = dist[a][b] + d;
			
			ans = max(ans, dist[x][y]);
			
			if(d == 1){
				dq.push_back({x,y});
			}
			else if(d == 0){
				dq.push_front({x,y});
			}
		}
		
	}
	return ans;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  
  int h, w; cin >> h >> w;
  
  for(int i = 0; i < h; i++){
	  for(int j = 0; j < w; j++){
		  char x; cin >> x;
		  meadow[i][j] = x;
	  }
  }
  cout << solve(h,w)+1;
  
  
	  
  
}

Subtask #1

25.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	30 ms	67932 KB	Output isn't correct
2	Correct	11 ms	66140 KB	Output is correct
3	Correct	12 ms	66140 KB	Output is correct
4	Correct	26 ms	68956 KB	Output is correct
5	Correct	14 ms	67164 KB	Output is correct
6	Correct	11 ms	66136 KB	Output is correct
7	Correct	11 ms	66140 KB	Output is correct
8	Incorrect	11 ms	66140 KB	Output isn't correct
9	Correct	12 ms	66396 KB	Output is correct
10	Correct	13 ms	66908 KB	Output is correct
11	Correct	14 ms	66904 KB	Output is correct
12	Correct	16 ms	67284 KB	Output is correct
13	Correct	13 ms	67164 KB	Output is correct
14	Correct	14 ms	67164 KB	Output is correct
15	Correct	25 ms	69980 KB	Output is correct
16	Incorrect	33 ms	68188 KB	Output isn't correct
17	Correct	21 ms	67980 KB	Output is correct
18	Correct	26 ms	69012 KB	Output is correct

Subtask #2

45.9375 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	633 ms	214868 KB	Output isn't correct
2	Correct	64 ms	75060 KB	Output is correct
3	Correct	278 ms	94164 KB	Output is correct
4	Incorrect	80 ms	79444 KB	Output isn't correct
5	Correct	196 ms	87892 KB	Output is correct
6	Correct	937 ms	119368 KB	Output is correct
7	Correct	666 ms	227104 KB	Output is correct
8	Incorrect	624 ms	213072 KB	Output isn't correct
9	Incorrect	11 ms	65884 KB	Output isn't correct
10	Incorrect	12 ms	65884 KB	Output isn't correct
11	Correct	708 ms	219712 KB	Output is correct
12	Correct	12 ms	66648 KB	Output is correct
13	Correct	60 ms	74964 KB	Output is correct
14	Incorrect	40 ms	71508 KB	Output isn't correct
15	Correct	32 ms	72016 KB	Output is correct
16	Incorrect	16 ms	66396 KB	Output isn't correct
17	Correct	133 ms	80088 KB	Output is correct
18	Correct	74 ms	79956 KB	Output is correct
19	Incorrect	77 ms	79440 KB	Output isn't correct
20	Incorrect	38 ms	72276 KB	Output isn't correct
21	Correct	211 ms	91096 KB	Output is correct
22	Correct	172 ms	88144 KB	Output is correct
23	Incorrect	205 ms	82256 KB	Output isn't correct
24	Correct	196 ms	95696 KB	Output is correct
25	Correct	255 ms	94288 KB	Output is correct
26	Correct	652 ms	192972 KB	Output is correct
27	Correct	815 ms	120444 KB	Output is correct
28	Correct	966 ms	119212 KB	Output is correct
29	Correct	943 ms	115672 KB	Output is correct
30	Correct	840 ms	123368 KB	Output is correct
31	Incorrect	716 ms	91812 KB	Output isn't correct
32	Correct	702 ms	124608 KB	Output is correct