oj.uz

Submission #78614

# Submission time Handle Problem Language Result Execution time Memory
78614 2018-10-06T17:13:13 Z bash Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 167716 KB 
/**
https://boi2013.informatik-olympiade.de/wp-content/uploads/2013/05/tracks-spoiler.pdf
*/
/**
SXR0aXAkI0JwbXptI3FhI3Z3I293bCNqY2IjUG0jMCNicG0jVHFkcXZvLyNCcG0jQW10bjBhY2phcWFicXZvLyNNYm16dml0MSNWdyNhdGN1am16I2tpdiNhbXF9bSNQcXUjVnd6I0F0bW14MSNQcWEjaXptI2l0dCNicHF2b2EjUXYjYnBtI3BtaWRtdmEjaXZsI3d2I21pemJwMSNFcHcjcWEjYnBtem0ja2l2I3F2Ym16a21sbSNRdiNQcWEjeHptYW12a20jbXtrbXhiI0lhI3BtI3htenVxYmJtYnBHI1BtI3N2d2VtYnAjRXBpYiMraXh4bWl6bWJwI2J3I1BxYSNrem1pYmN6bWEjSWEsI0ptbnd6bSN3eiNJbmJteiN3eiNKbXBxdmwjYnBtdTEjVnd6I2FwaXR0I2JwbXwja3d1eGlhYSNJY29wYiN3biNwcWEjc3Z3ZXRtbG9tI017a214YiNpYSNQbSNlcXR0bWJwMSNQcWEjYnB6d3ZtI2x3YnAjbXtibXZsI1dkbXojYnBtI3BtaWRtdmEjSXZsI3d2I21pemJwLyNpdmwjUG0jbm1tdG1icCNWdyNuaWJxb2NtI3F2I29jaXpscXZvI0l2bCN4em1hbXpkcXZvI2JwbXUvI053eiNQbSNxYSNicG0jVXdhYiNQcW9wMSNCcG0jQWN4em11bSMrcXYjb3R3enwsMQ==
*/
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#pragma GCC optimize("Ofast")
 
#define F first
#define S second
#define endl '\n'
#define deb(x) cout<<#x<<' '<<x<<endl;
#define pb push_back
 
/*
#ifdef IZI_KATKA
#define int __int64_t
#else
#define int __int64
#endif
*/
 
const long long MOD = 1e9 + 7;
const long long MAXN = 1e6 + 1;
using namespace std;
 
typedef long long ll;
 
long long readInt() {
    bool minus1 = false;
    long long result = 0;
    char ch;
    ch = getchar();
    while (true) {
        if (ch == '-') break;
        if (ch >= '0' && ch <= '9') break;
        ch = getchar();
    }
    if (ch == '-') minus1 = true; else result = ch-'0';
    while (true) {
        ch = getchar();
        if (ch < '0' || ch > '9') break;
        result = result*10 + (ch - '0');
    }
    if (minus1)
        return -result;
    else
        return result;
}
 
 
/************************************************************************************************/
static struct IO {char tmp[1 << 10];char cur;inline char nextChar()
{ return cur = getc_unlocked(stdin); }inline char peekChar() { return cur; }
inline operator bool() { return peekChar(); }inline static bool isBlank(char c)
{ return (c < '-' && c); }inline bool skipBlanks()
{ while (isBlank(nextChar())); return peekChar() != 0; }
inline IO& operator >> (char & c) { c = nextChar(); return *this; }
inline IO& operator >> (char * buf) {if (skipBlanks()) {if (peekChar()) {*(buf++) = peekChar();
while (!isBlank(nextChar())) *(buf++) = peekChar();} *(buf++) = 0; } return *this; }
inline IO& operator >> (string & s) {if (skipBlanks()) {	s.clear(); s += peekChar();
while (!isBlank(nextChar())) s += peekChar(); }return *this; }
inline IO& operator >> (double & d) { if ((*this) >> tmp) sscanf(tmp, "%lf", &d); return *this;	}
#define defineInFor(intType) inline IO& operator >>(intType & n) { if (skipBlanks()) { \
int sign = +1; if (peekChar() == '-') { sign = -1; n = nextChar() - '0'; } else \
n = peekChar() - '0'; while (!isBlank(nextChar())) { n += n + (n << 3) + peekChar() - 48; } \
n *= sign; } return *this; }
defineInFor(int)defineInFor(unsigned int)defineInFor(long long)
inline void putChar(char c) { putc_unlocked(c, stdout); }inline IO& operator << (char c) { putChar(c); return *this; }
inline IO& operator << (const char * s) { while (*s) putChar(*s++); return *this; }
inline IO& operator << (const string & s) { for (int i = 0; i < (int)s.size(); ++i) putChar(s[i]); return *this; }
char * toString(double d) { sprintf(tmp, "%lf%c", d, '\0'); return tmp; }
inline IO& operator << (double d) { return (*this) << toString(d); }
#define defineOutFor(intType) inline char * toString(intType n) { char * p = (tmp + 30); \
if (n) { bool isNeg = 0; if (n < 0) isNeg = 1, n = -n; while (n) *--p = (n % 10) + '0', n /= 10; \
if (isNeg) *--p = '-'; } else *--p = '0'; return p; } inline IO& operator << (intType n) { return (*this) << toString(n); }
defineOutFor(int)defineOutFor(long long)
#define endl ('\n')
#define cout __io__
#define cin __io__
} __io__;
/**************************************************************************************************/
 
 
const int N = 4001;
 
char a[N][N];
 
int d[N][N];
 
int d_x[] = {1, -1, 0, 0};
int d_y[] = {0, 0, 1, -1};
 
int H, W; 
 
int main() {
	ios_base::sync_with_stdio(0);
	H = readInt(), W = readInt();
    for (int i = 1; i <= H; i++) {
    	for (int j = 1; j <= W; j++) {
    		cin >> a[i][j];
        	d[i][j] = MOD;
    	}
    }
	deque<pair <int, int> > q;
	q.push_front({1, 1});       
	d[1][1] = 0;
	int mx = 0;
	while (!q.empty()) {
		pair <int, int> v = q.front();
		q.pop_front();
		int x = v.F;
		int y = v.S;
		//cerr << v.F << ' ' << v.S << endl;
		for (int i = 0; i < 4; i++) {
			int X = v.first + d_x[i];
			int Y = v.second + d_y[i]; 
			if (X >= 1 && Y >= 1 && X <= H && Y <= W && a[X][Y] != '.') {
				if (d[X][Y] > d[x][y] + (a[X][Y] != a[x][y])) {
					d[X][Y] = d[x][y] + (a[X][Y] != a[x][y]);
					if ((a[X][Y] != a[x][y])) {
						q.push_front({X, Y});
					} else {
						q.pb({X, Y});
					}	 	
				}
			}
		}
	}
	
	for (int i =1 ; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			if (a[i][j] != '.')
			mx = max(mx, d[i][j]);
			//cout << d[i][j] << ' ';
		}
		//cout << endl;
	}
	cout << mx+1;
	return 0;
}

Compilation message

tracks.cpp:99:0: warning: "endl" redefined
 #define endl ('\n')
 
tracks.cpp:32:0: note: this is the location of the previous definition
 #define endl '\n'

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1905 ms 6652 KB Output isn't correct
2 Incorrect 3 ms 6652 KB Output isn't correct
3 Incorrect 3 ms 6652 KB Output isn't correct
4 Incorrect 353 ms 6652 KB Output isn't correct
5 Incorrect 4 ms 6652 KB Output isn't correct
6 Incorrect 2 ms 6652 KB Output isn't correct
7 Incorrect 2 ms 6652 KB Output isn't correct
8 Incorrect 6 ms 6652 KB Output isn't correct
9 Incorrect 3 ms 6652 KB Output isn't correct
10 Incorrect 4 ms 6652 KB Output isn't correct
11 Incorrect 64 ms 6652 KB Output isn't correct
12 Incorrect 320 ms 6652 KB Output isn't correct
13 Incorrect 4 ms 6652 KB Output isn't correct
14 Incorrect 5 ms 6652 KB Output isn't correct
15 Incorrect 783 ms 6652 KB Output isn't correct
16 Incorrect 1842 ms 6944 KB Output isn't correct
17 Incorrect 7 ms 6944 KB Output isn't correct
18 Incorrect 376 ms 6944 KB Output isn't correct

Subtask #2
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 31100 KB Output isn't correct
2 Incorrect 90 ms 31100 KB Output isn't correct
3 Incorrect 176 ms 78936 KB Output isn't correct
4 Incorrect 46 ms 78936 KB Output isn't correct
5 Execution timed out 2077 ms 78936 KB Time limit exceeded
6 Execution timed out 2085 ms 167716 KB Time limit exceeded
7 Incorrect 25 ms 167716 KB Output isn't correct
8 Incorrect 25 ms 167716 KB Output isn't correct
9 Incorrect 536 ms 167716 KB Output isn't correct
10 Incorrect 2 ms 167716 KB Output isn't correct
11 Incorrect 26 ms 167716 KB Output isn't correct
12 Incorrect 3 ms 167716 KB Output isn't correct
13 Incorrect 102 ms 167716 KB Output isn't correct
14 Incorrect 29 ms 167716 KB Output isn't correct
15 Incorrect 16 ms 167716 KB Output isn't correct
16 Incorrect 9 ms 167716 KB Output isn't correct
17 Incorrect 47 ms 167716 KB Output isn't correct
18 Incorrect 45 ms 167716 KB Output isn't correct
19 Incorrect 46 ms 167716 KB Output isn't correct
20 Incorrect 79 ms 167716 KB Output isn't correct
21 Incorrect 91 ms 167716 KB Output isn't correct
22 Execution timed out 2078 ms 167716 KB Time limit exceeded
23 Incorrect 543 ms 167716 KB Output isn't correct
24 Incorrect 95 ms 167716 KB Output isn't correct
25 Incorrect 155 ms 167716 KB Output isn't correct
26 Execution timed out 2065 ms 167716 KB Time limit exceeded
27 Execution timed out 2062 ms 167716 KB Time limit exceeded
28 Execution timed out 2078 ms 167716 KB Time limit exceeded
29 Execution timed out 2072 ms 167716 KB Time limit exceeded
30 Execution timed out 2067 ms 167716 KB Time limit exceeded
31 Execution timed out 2057 ms 167716 KB Time limit exceeded
32 Execution timed out 2075 ms 167716 KB Time limit exceeded