oj.uz

Submission #350151

# Submission time Handle Problem Language Result Execution time Memory
350151 2021-01-19T03:03:25 Z ignaciocanta Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 629 ms 132732 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
using tint = long long;
using ld = long double;
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
using pi = pair<int,int>;
using pl = pair<tint,tint>;
using vi = vector<int>;
using vpi = vector<pi>;
using vvi = vector<vi>;
using vl = vector<tint>;
using vb = vector<bool>;

#define pb push_back
#define pf push_front
#define rsz resize
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend() 
#define sz(x) (int)(x).size()
#define ins insert

#define f first
#define s second
#define mp make_pair
 
#define DBG(x) cerr << #x << " = " << x << endl;
 
const int MOD = 1e9+7;
const tint mod = 998244353;
const int MX = 4005; 
const tint INF = 1e18; 
const int inf = 2e9;
const ld PI = acos(ld(-1)); 
const ld eps = 1e-8;
 
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
 
template<class T> void remDup(vector<T> &v){ 
    sort(all(v)); v.erase(unique(all(v)),end(v));
}
 
bool valid(int x, int y, int n, int m){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int cdiv(int a, int b) { return a/b+((a^b)>0&&a%b); } //redondea p arriba
int fdiv(int a, int b) { return a/b-((a^b)<0&&a%b); } //redonde p abajo
 
void NACHO(string name = ""){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(sz(name)){
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

string tab[MX];
bool visited[MX][MX];
int dist[MX][MX];

int main(){
	NACHO();
	int n, m; cin >> n >> m;
	F0R(i, n) cin >> tab[i];
	visited[0][0] = 1;
	dist[0][0] = 1;
	deque<pi> q;
	q.pf(mp(0, 0));
	int ret = 0;
	while(sz(q)){
		auto u = q.front();
		q.pop_front();
		int x = u.f, y = u.s;
		ret = max(ret, dist[x][y]);
		F0R(k, 4){
			int xx = x+dx[k], yy = y+dy[k];
			if(valid(xx, yy, n, m) && !visited[xx][yy] && tab[xx][yy] != '.'){
				int w = (tab[x][y] != tab[xx][yy] ? 1 : 0);
				visited[xx][yy] = 1;
				dist[xx][yy] = dist[x][y]+w;
				if(w == 0){
					q.pf(mp(xx, yy));
				}else q.pb(mp(xx, yy));
			} 
		}
	}
	cout << ret << "\n";
}

Compilation message

tracks.cpp: In function 'void NACHO(std::string)':
tracks.cpp:61:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:62:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   62 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5612 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 8 ms 5356 KB Output is correct
5 Correct 5 ms 3180 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 1004 KB Output is correct
9 Correct 2 ms 1260 KB Output is correct
10 Correct 3 ms 2668 KB Output is correct
11 Correct 3 ms 2284 KB Output is correct
12 Correct 6 ms 3308 KB Output is correct
13 Correct 4 ms 3180 KB Output is correct
14 Correct 3 ms 3180 KB Output is correct
15 Correct 11 ms 5484 KB Output is correct
16 Correct 17 ms 5740 KB Output is correct
17 Correct 10 ms 5376 KB Output is correct
18 Correct 8 ms 5356 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 30984 KB Output is correct
2 Correct 45 ms 15340 KB Output is correct
3 Correct 191 ms 75508 KB Output is correct
4 Correct 79 ms 33200 KB Output is correct
5 Correct 148 ms 54508 KB Output is correct
6 Correct 629 ms 110084 KB Output is correct
7 Correct 22 ms 32364 KB Output is correct
8 Correct 27 ms 30956 KB Output is correct
9 Correct 2 ms 876 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 21 ms 31724 KB Output is correct
12 Correct 2 ms 1772 KB Output is correct
13 Correct 44 ms 15340 KB Output is correct
14 Correct 28 ms 10604 KB Output is correct
15 Correct 24 ms 13292 KB Output is correct
16 Correct 19 ms 5996 KB Output is correct
17 Correct 112 ms 29292 KB Output is correct
18 Correct 93 ms 36204 KB Output is correct
19 Correct 72 ms 33132 KB Output is correct
20 Correct 53 ms 26092 KB Output is correct
21 Correct 122 ms 53740 KB Output is correct
22 Correct 133 ms 54508 KB Output is correct
23 Correct 217 ms 44780 KB Output is correct
24 Correct 125 ms 50924 KB Output is correct
25 Correct 443 ms 96492 KB Output is correct
26 Correct 378 ms 132732 KB Output is correct
27 Correct 526 ms 123164 KB Output is correct
28 Correct 616 ms 110116 KB Output is correct
29 Correct 619 ms 108512 KB Output is correct
30 Correct 565 ms 112624 KB Output is correct
31 Correct 548 ms 74732 KB Output is correct
32 Correct 434 ms 108540 KB Output is correct