oj.uz

Submission #78615

# Submission time Handle Problem Language Result Execution time Memory
78615 2018-10-06T17:14:11 Z bash Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 165436 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);
	cin >> H>>W;
    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 1973 ms 6740 KB Output isn't correct
2 Incorrect 2 ms 6740 KB Output isn't correct
3 Incorrect 2 ms 6740 KB Output isn't correct
4 Incorrect 373 ms 6740 KB Output isn't correct
5 Incorrect 4 ms 6740 KB Output isn't correct
6 Incorrect 3 ms 6740 KB Output isn't correct
7 Incorrect 2 ms 6740 KB Output isn't correct
8 Incorrect 7 ms 6740 KB Output isn't correct
9 Incorrect 3 ms 6740 KB Output isn't correct
10 Incorrect 4 ms 6740 KB Output isn't correct
11 Incorrect 69 ms 6740 KB Output isn't correct
12 Incorrect 329 ms 6740 KB Output isn't correct
13 Incorrect 4 ms 6740 KB Output isn't correct
14 Incorrect 4 ms 6740 KB Output isn't correct
15 Incorrect 839 ms 6740 KB Output isn't correct
16 Incorrect 1924 ms 6912 KB Output isn't correct
17 Incorrect 8 ms 6912 KB Output isn't correct
18 Incorrect 385 ms 6912 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 92 ms 31100 KB Output isn't correct
3 Incorrect 181 ms 78972 KB Output isn't correct
4 Incorrect 50 ms 78972 KB Output isn't correct
5 Execution timed out 2073 ms 78972 KB Time limit exceeded
6 Execution timed out 2075 ms 160188 KB Time limit exceeded
7 Incorrect 26 ms 160188 KB Output isn't correct
8 Incorrect 25 ms 160188 KB Output isn't correct
9 Incorrect 592 ms 160188 KB Output isn't correct
10 Incorrect 2 ms 160188 KB Output isn't correct
11 Incorrect 26 ms 160188 KB Output isn't correct
12 Incorrect 3 ms 160188 KB Output isn't correct
13 Incorrect 96 ms 160188 KB Output isn't correct
14 Incorrect 30 ms 160188 KB Output isn't correct
15 Incorrect 19 ms 160188 KB Output isn't correct
16 Incorrect 10 ms 160188 KB Output isn't correct
17 Incorrect 49 ms 160188 KB Output isn't correct
18 Incorrect 46 ms 160188 KB Output isn't correct
19 Incorrect 48 ms 160188 KB Output isn't correct
20 Incorrect 80 ms 160188 KB Output isn't correct
21 Incorrect 89 ms 160188 KB Output isn't correct
22 Execution timed out 2068 ms 160188 KB Time limit exceeded
23 Incorrect 523 ms 160188 KB Output isn't correct
24 Incorrect 97 ms 160188 KB Output isn't correct
25 Incorrect 157 ms 160188 KB Output isn't correct
26 Execution timed out 2066 ms 160188 KB Time limit exceeded
27 Execution timed out 2054 ms 160188 KB Time limit exceeded
28 Execution timed out 2072 ms 165436 KB Time limit exceeded
29 Execution timed out 2078 ms 165436 KB Time limit exceeded
30 Execution timed out 2076 ms 165436 KB Time limit exceeded
31 Execution timed out 2060 ms 165436 KB Time limit exceeded
32 Execution timed out 2064 ms 165436 KB Time limit exceeded