oj.uz

Submission #992100

# Submission time Handle Problem Language Result Execution time Memory
992100 2024-06-03T23:01:32 Z ahoraSoyPeor Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1739 ms 342904 KB 
#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;
		}
	}
}

const int delta_X[] = {-1, 1, 0, 0};
const int delta_Y[] = {0, 0, -1, 1};

bool is_in ( pii cell, int h, int w ) {
    return cell.ff >= 0 and cell.ss >= 0 and cell.ff < h and cell.ss < w;
}

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;
        for ( int i = 0; i < 4; ++i ) {
            pii nxt_cell = {a+delta_X[i], b+delta_Y[i]};
            if ( !is_in ( nxt_cell, h, w ) ) continue;
            char animal_cell = meadow[nxt_cell.ff][nxt_cell.ss];
            if ( animal_cell != '.' )
                vecinos.pb ( nxt_cell );
        }
		
		// 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; 
}

/*
 * 
 * 5 8
FFR.....
.FRRR...
.FFFFF..
..RRRFFR
.....FFF

5 5
FRFRF
RRFRF
FFFRF
RRRRF
FFFFF
 */

Compilation message

tracks.cpp: In function 'int solve(int, int)':
tracks.cpp:41:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto [a, b] = dq.front(); dq.pop_front();
      |        ^
tracks.cpp:57:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |   for(auto [x,y]: vecinos){
      |            ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 67932 KB Output is correct
2 Correct 16 ms 66288 KB Output is correct
3 Correct 15 ms 66232 KB Output is correct
4 Correct 35 ms 68352 KB Output is correct
5 Correct 20 ms 67164 KB Output is correct
6 Correct 16 ms 66392 KB Output is correct
7 Correct 16 ms 66140 KB Output is correct
8 Correct 17 ms 66280 KB Output is correct
9 Correct 16 ms 66396 KB Output is correct
10 Correct 18 ms 66908 KB Output is correct
11 Correct 19 ms 66908 KB Output is correct
12 Correct 24 ms 67248 KB Output is correct
13 Correct 18 ms 67164 KB Output is correct
14 Correct 18 ms 67136 KB Output is correct
15 Correct 36 ms 69980 KB Output is correct
16 Correct 43 ms 67932 KB Output is correct
17 Correct 31 ms 67912 KB Output is correct
18 Correct 34 ms 68340 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 93528 KB Output is correct
2 Correct 97 ms 75060 KB Output is correct
3 Correct 429 ms 94412 KB Output is correct
4 Correct 112 ms 79444 KB Output is correct
5 Correct 308 ms 88016 KB Output is correct
6 Correct 1710 ms 123484 KB Output is correct
7 Correct 27 ms 94244 KB Output is correct
8 Correct 27 ms 93528 KB Output is correct
9 Correct 17 ms 66136 KB Output is correct
10 Correct 17 ms 66204 KB Output is correct
11 Correct 25 ms 94044 KB Output is correct
12 Correct 17 ms 66664 KB Output is correct
13 Correct 93 ms 75344 KB Output is correct
14 Correct 61 ms 71768 KB Output is correct
15 Correct 43 ms 72028 KB Output is correct
16 Correct 55 ms 67676 KB Output is correct
17 Correct 213 ms 80092 KB Output is correct
18 Correct 119 ms 79956 KB Output is correct
19 Correct 111 ms 79576 KB Output is correct
20 Correct 150 ms 79116 KB Output is correct
21 Correct 263 ms 88524 KB Output is correct
22 Correct 295 ms 88012 KB Output is correct
23 Correct 404 ms 84056 KB Output is correct
24 Correct 258 ms 90452 KB Output is correct
25 Correct 478 ms 94436 KB Output is correct
26 Correct 1220 ms 342904 KB Output is correct
27 Correct 1569 ms 152476 KB Output is correct
28 Correct 1739 ms 123360 KB Output is correct
29 Correct 1625 ms 117168 KB Output is correct
30 Correct 1610 ms 137080 KB Output is correct
31 Correct 1161 ms 91728 KB Output is correct
32 Correct 1342 ms 160780 KB Output is correct