oj.uz

Submission #78608

# Submission time Handle Problem Language Result Execution time Memory
78608 2018-10-06T16:51:45 Z bash Tracks in the Snow (BOI13_tracks) C++17
57.2917 / 100
 2000 ms 80972 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>
 
#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;
}
 
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() {
	#ifdef IZI_KATKA
	assert(freopen("input", "r", stdin));
    assert(freopen("output", "w", stdout));
    #endif
    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;
}

Subtask #1
26.6666666667 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2051 ms 6264 KB Time limit exceeded
2 Correct 2 ms 6264 KB Output is correct
3 Correct 3 ms 6264 KB Output is correct
4 Correct 449 ms 6264 KB Output is correct
5 Correct 91 ms 6264 KB Output is correct
6 Correct 2 ms 6264 KB Output is correct
7 Correct 4 ms 6264 KB Output is correct
8 Correct 7 ms 6264 KB Output is correct
9 Correct 4 ms 6264 KB Output is correct
10 Correct 62 ms 6264 KB Output is correct
11 Correct 53 ms 6264 KB Output is correct
12 Correct 471 ms 6264 KB Output is correct
13 Correct 92 ms 6264 KB Output is correct
14 Correct 92 ms 6264 KB Output is correct
15 Correct 1661 ms 6264 KB Output is correct
16 Execution timed out 2049 ms 6312 KB Time limit exceeded
17 Correct 992 ms 6312 KB Output is correct
18 Correct 509 ms 6312 KB Output is correct

Subtask #2
30.625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31020 KB Output is correct
2 Execution timed out 2069 ms 31020 KB Time limit exceeded
3 Execution timed out 2059 ms 79152 KB Time limit exceeded
4 Execution timed out 2054 ms 79152 KB Time limit exceeded
5 Correct 901 ms 79152 KB Output is correct
6 Execution timed out 2059 ms 80840 KB Time limit exceeded
7 Correct 30 ms 80840 KB Output is correct
8 Correct 29 ms 80840 KB Output is correct
9 Correct 635 ms 80840 KB Output is correct
10 Correct 4 ms 80840 KB Output is correct
11 Correct 29 ms 80840 KB Output is correct
12 Correct 5 ms 80840 KB Output is correct
13 Execution timed out 2071 ms 80840 KB Time limit exceeded
14 Execution timed out 2049 ms 80840 KB Time limit exceeded
15 Correct 105 ms 80840 KB Output is correct
16 Execution timed out 2062 ms 80840 KB Time limit exceeded
17 Execution timed out 2084 ms 80840 KB Time limit exceeded
18 Correct 398 ms 80840 KB Output is correct
19 Execution timed out 2076 ms 80840 KB Time limit exceeded
20 Execution timed out 2066 ms 80840 KB Time limit exceeded
21 Execution timed out 2079 ms 80840 KB Time limit exceeded
22 Correct 766 ms 80840 KB Output is correct
23 Execution timed out 2053 ms 80840 KB Time limit exceeded
24 Correct 758 ms 80840 KB Output is correct
25 Correct 1535 ms 80840 KB Output is correct
26 Correct 1423 ms 80840 KB Output is correct
27 Execution timed out 2037 ms 80840 KB Time limit exceeded
28 Execution timed out 2071 ms 80972 KB Time limit exceeded
29 Execution timed out 2069 ms 80972 KB Time limit exceeded
30 Execution timed out 2070 ms 80972 KB Time limit exceeded
31 Execution timed out 2074 ms 80972 KB Time limit exceeded
32 Execution timed out 2053 ms 80972 KB Time limit exceeded