oj.uz

답안 #416861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
416861 2021-06-03T06:22:17 Z Recedivies Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 900 ms 130888 KB 
/*
 * Author : recedivies
 * Problem Link : https://tlx.toki.id/problems/osn-2017/2B/
 * Mei 20, 2021
 */
#include <bits/stdc++.h>
using namespace std; 

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef string str;

#define io() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sz(a) ((int)(a).size())
#define mset(a, b) memset(a, b, sizeof(a))
#define print(a, n) for(int _i = 0 ; _i < n ; _i++) cout << a[_i] << " "; cout << '\n';
#define print2(a, n, m) for(int _i = 0 ; _i < n ; _i++){for(int _j = 0 ; _j < m ; _j++){cout << a[_i][_j] << " ";} cout << '\n';}

int dd[123];

ll Read() {
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    ch = getchar();
  }
  ll v = 0;
  while ('0' <= ch && ch <= '9') {
    v = v * 10 + (int) (ch - '0');
    ch = getchar();
  }
  return v;
}
 
void Write(ll x) {
  int len = 0;
  while (x > 0) {
    dd[len++] = x % 10;
    x /= 10;
  }
  for (int i = len - 1; i >= 0; i--) {
    putchar('0' + dd[i]);
  }
  if (len == 0) {
    putchar('0');
  }
  putchar(' ');
}

template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
    return os << "(" << p.first << ", " << p.second << ")";
}
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
    os << "{";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if ( it != v.begin() )
            os << ", ";
        os << *it;
    }
    return os << "}";
}
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if ( it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "]";
}
template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if ( it != v.begin() )
            os << ", ";
        os << it -> first << " = " << it -> second ;
    }
    return os << "]\n";
}
#define deb(args...) do {cerr << #args << " = "; faltu(args); } while(0)
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define time(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false); debug("%s Time : %.4fs", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))

void faltu () {
    cerr << endl;
}
template <typename T>
void faltu( T a[], int n ) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) {
    cerr << arg << ' ';
    faltu(rest...);
}
 
template <class T> T egcd(T a , T b , T &x , T &y){T gcd , xt , yt;if(a == 0){gcd = b;x = 0 , y = 1;}else {gcd = egcd(b % a , a , xt , yt);x = yt - (b/a)*xt; y = xt;}return gcd;}
template <class T> T expo(T base , T exp , T mod){T res = 1;base = base % mod;while (exp > 0){if (exp & 1)res = (res*base) % mod;exp = exp>>1;base = (base*base) % mod;}return res;}
template <class T> T modinv(T a , T mod){T x , y; egcd<T>(a , mod , x , y);while(x < 0) x += mod; while(x >= mod) x -= mod; return x;}
template <class T> T modinvfermat(T a , T mod){return expo<T>(a , mod - 2 , mod);}
template <class T> bool rev(T a , T b){return a > b;}
template <class T> ll maxpower(T a , T b){ll ans = 0;while(a > 0 && a % b == 0){ans++;a /= b;}return ans;}
template <class T> T mceil(T a, T b){if(a % b == 0) return a/b; else return a/b + 1;}
template <class T> T lcm(T a, T b){return (a)/__gcd<T>(a, b)*(b);}

//const int MOD = (119 << 23) + 1;
const int MOD = 1e9 + 7;
const ll INF = (ll) 1e18;
const double PI = acos(-1);
const double EPS = 1e-9;
const int MAX = 2e9;
const int dx[4] = {+1, 0, -1, 0};
const int dy[4] = {0, +1, 0, -1};
//const int dx[8] = {+1, +1, -1, -1, 0, 0, +1, -1};
//const int dy[8] = {+1, -1, -1, +1, +1, -1, 0, 0};
const int N = 4001;

char a[N][N];
int dist[N][N];
int n, m;

bool isValid(int i, int j) {
	return i >= 0 && j >= 0 && i < n && j < m;
}

int main() {
	io();
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dist[i][j] = MAX;
			cin >> a[i][j];
		}
	}
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	dist[0][0] = 0;
	while (!q.empty()) {
		int u = q.front().first, v = q.front().second;
		q.pop_front();
		for (int k = 0; k < 4; k++) {
			int r = dx[k] + u;
			int c = dy[k] + v;
			
			if (isValid(r, c) && a[r][c] != '.' && dist[r][c] > dist[u][v] + 1) {
				if (a[r][c] == a[u][v]) {
					dist[r][c] = dist[u][v];
					q.push_front({r, c});
				} else {
					dist[r][c] = dist[u][v] + 1;
					q.push_back({r, c});
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (dist[i][j] != MAX) ans = max(ans, dist[i][j] + 1);
		}
	}
	cout << ans << '\n';
	return 0;
}
/*
5 8
FFR.....
.FRRF...
.RRFFFFF
..RRRFFR
.....FFF

*/

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 5448 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 10 ms 5164 KB Output is correct
5 Correct 4 ms 2976 KB Output is correct
6 Correct 1 ms 448 KB Output is correct
7 Correct 1 ms 700 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 1100 KB Output is correct
10 Correct 4 ms 2508 KB Output is correct
11 Correct 3 ms 2120 KB Output is correct
12 Correct 7 ms 3020 KB Output is correct
13 Correct 4 ms 3020 KB Output is correct
14 Correct 5 ms 3020 KB Output is correct
15 Correct 14 ms 5548 KB Output is correct
16 Correct 15 ms 5432 KB Output is correct
17 Correct 13 ms 5196 KB Output is correct
18 Correct 12 ms 5204 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 30796 KB Output is correct
2 Correct 63 ms 17880 KB Output is correct
3 Correct 443 ms 94188 KB Output is correct
4 Correct 138 ms 33604 KB Output is correct
5 Correct 265 ms 67748 KB Output is correct
6 Correct 887 ms 108292 KB Output is correct
7 Correct 16 ms 32204 KB Output is correct
8 Correct 16 ms 30788 KB Output is correct
9 Correct 3 ms 588 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 16 ms 31596 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 69 ms 17816 KB Output is correct
14 Correct 37 ms 11844 KB Output is correct
15 Correct 38 ms 13032 KB Output is correct
16 Correct 28 ms 6596 KB Output is correct
17 Correct 161 ms 36060 KB Output is correct
18 Correct 141 ms 35780 KB Output is correct
19 Correct 126 ms 33544 KB Output is correct
20 Correct 103 ms 31012 KB Output is correct
21 Correct 262 ms 70084 KB Output is correct
22 Correct 266 ms 67824 KB Output is correct
23 Correct 309 ms 56764 KB Output is correct
24 Correct 263 ms 69444 KB Output is correct
25 Correct 702 ms 94236 KB Output is correct
26 Correct 598 ms 130888 KB Output is correct
27 Correct 815 ms 128844 KB Output is correct
28 Correct 900 ms 108428 KB Output is correct
29 Correct 899 ms 105720 KB Output is correct
30 Correct 840 ms 111424 KB Output is correct
31 Correct 615 ms 73476 KB Output is correct
32 Correct 727 ms 118520 KB Output is correct