oj.uz

Submission #416869

# Submission time Handle Problem Language Result Execution time Memory
416869 2021-06-03T06:34:03 Z Recedivies Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1517 ms 124656 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], ch;
int dist[N][N];
int n, m;

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

int main() {
	scanf("%d %d%c", &n, &m, &ch);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			dist[i][j] = MAX;
			scanf("%c", &a[i][j]);
		}
		scanf("%c", &ch);
	}
	deque<pair<int, int>> q;
	q.push_front({0, 0});
	dist[0][0] = 0;
	int ans = 0;
	while (!q.empty()) {
		int u = q.front().first, v = q.front().second;
		ans = max(ans, dist[u][v] + 1);
		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});
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}
/*

*/

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:140:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |  scanf("%d %d%c", &n, &m, &ch);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
tracks.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |    scanf("%c", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~
tracks.cpp:146:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |   scanf("%c", &ch);
      |   ~~~~~^~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5324 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 16 ms 5076 KB Output is correct
5 Correct 7 ms 2892 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 684 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 2 ms 1072 KB Output is correct
10 Correct 6 ms 2508 KB Output is correct
11 Correct 5 ms 2124 KB Output is correct
12 Correct 10 ms 3020 KB Output is correct
13 Correct 7 ms 2892 KB Output is correct
14 Correct 7 ms 2892 KB Output is correct
15 Correct 26 ms 5436 KB Output is correct
16 Correct 24 ms 5312 KB Output is correct
17 Correct 22 ms 5264 KB Output is correct
18 Correct 16 ms 5112 KB Output is correct

Subtask #2
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 30796 KB Output is correct
2 Correct 126 ms 17864 KB Output is correct
3 Correct 995 ms 84408 KB Output is correct
4 Correct 257 ms 33556 KB Output is correct
5 Correct 603 ms 64776 KB Output is correct
6 Correct 1517 ms 98380 KB Output is correct
7 Correct 21 ms 32256 KB Output is correct
8 Correct 19 ms 30876 KB Output is correct
9 Correct 5 ms 588 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 21 ms 31612 KB Output is correct
12 Correct 3 ms 1484 KB Output is correct
13 Correct 123 ms 17760 KB Output is correct
14 Correct 69 ms 11844 KB Output is correct
15 Correct 73 ms 13088 KB Output is correct
16 Correct 55 ms 6716 KB Output is correct
17 Correct 310 ms 36052 KB Output is correct
18 Correct 288 ms 35656 KB Output is correct
19 Correct 274 ms 33484 KB Output is correct
20 Correct 225 ms 30940 KB Output is correct
21 Correct 590 ms 66708 KB Output is correct
22 Correct 634 ms 64940 KB Output is correct
23 Correct 586 ms 55016 KB Output is correct
24 Correct 638 ms 66300 KB Output is correct
25 Correct 1252 ms 84332 KB Output is correct
26 Correct 1004 ms 124656 KB Output is correct
27 Correct 1351 ms 118880 KB Output is correct
28 Correct 1447 ms 98176 KB Output is correct
29 Correct 1460 ms 95804 KB Output is correct
30 Correct 1377 ms 101700 KB Output is correct
31 Correct 979 ms 69092 KB Output is correct
32 Correct 1263 ms 108284 KB Output is correct