답안 #78598 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78598	2018-10-06T16:15:44 Z	bash	Tracks in the Snow (BOI13_tracks)	C++17	55.625 / 100	2000 ms	291328 KB

tracks

/**
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 = 4444;

char a[N][N];

bool used[N][N];
int d[N][N];

int timer = 0;

int d_x[] = {1, -1, 0, 0};
int d_y[] = {0, 0, 1, -1};

int H, W;

bool norm(int x1, int y1) {
	if (x1 >= 1 && y1 >= 1 && x1 <= H && y1 <= W) {
		if (a[x1][y1] != '.' && !used[x1][y1]) {
			return 1;			
		} else {
			return 0;
		}
	} else {
		return 0;
	}
}


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];
    	}
    }
    for (int i = 1; i <= H; i++) {
    	for (int j = 1; j <= W; j++) {
    		d[i][j] = MOD;
    	}
    }
	deque<pair <int, int> > q;
	q.push_front({1, 1});       
	used[1][1] = true;
	d[1][1] = 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 (norm(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});
					}	 	
				}
			}
		}
	}
	int mx = 0;
	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
25.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2043 ms	6904 KB	Time limit exceeded
2	Correct	2 ms	6904 KB	Output is correct
3	Correct	3 ms	6904 KB	Output is correct
4	Correct	671 ms	6904 KB	Output is correct
5	Correct	119 ms	6904 KB	Output is correct
6	Correct	2 ms	6904 KB	Output is correct
7	Correct	3 ms	6904 KB	Output is correct
8	Correct	8 ms	6904 KB	Output is correct
9	Correct	5 ms	6904 KB	Output is correct
10	Correct	84 ms	6904 KB	Output is correct
11	Correct	105 ms	6904 KB	Output is correct
12	Correct	606 ms	6904 KB	Output is correct
13	Correct	116 ms	6904 KB	Output is correct
14	Correct	118 ms	6904 KB	Output is correct
15	Execution timed out	2009 ms	7576 KB	Time limit exceeded
16	Execution timed out	2061 ms	8060 KB	Time limit exceeded
17	Correct	1226 ms	8060 KB	Output is correct
18	Correct	639 ms	8060 KB	Output is correct

Subtask #2
30.625 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Correct	32 ms	33388 KB	Output is correct
2	Execution timed out	2051 ms	33388 KB	Time limit exceeded
3	Execution timed out	2051 ms	106904 KB	Time limit exceeded
4	Execution timed out	2043 ms	106904 KB	Time limit exceeded
5	Correct	823 ms	106904 KB	Output is correct
6	Execution timed out	2059 ms	136440 KB	Time limit exceeded
7	Correct	35 ms	136440 KB	Output is correct
8	Correct	33 ms	136440 KB	Output is correct
9	Correct	746 ms	136440 KB	Output is correct
10	Correct	4 ms	136440 KB	Output is correct
11	Correct	34 ms	136440 KB	Output is correct
12	Correct	5 ms	136440 KB	Output is correct
13	Execution timed out	2049 ms	136440 KB	Time limit exceeded
14	Execution timed out	2054 ms	136440 KB	Time limit exceeded
15	Correct	128 ms	136440 KB	Output is correct
16	Execution timed out	2052 ms	136440 KB	Time limit exceeded
17	Execution timed out	2058 ms	136440 KB	Time limit exceeded
18	Correct	366 ms	136440 KB	Output is correct
19	Execution timed out	2049 ms	136440 KB	Time limit exceeded
20	Execution timed out	2056 ms	136440 KB	Time limit exceeded
21	Execution timed out	2062 ms	138540 KB	Time limit exceeded
22	Correct	790 ms	145412 KB	Output is correct
23	Execution timed out	2049 ms	145412 KB	Time limit exceeded
24	Correct	751 ms	163300 KB	Output is correct
25	Correct	1552 ms	202684 KB	Output is correct
26	Correct	1855 ms	203012 KB	Output is correct
27	Execution timed out	2073 ms	229708 KB	Time limit exceeded
28	Execution timed out	2041 ms	245552 KB	Time limit exceeded
29	Execution timed out	2068 ms	259584 KB	Time limit exceeded
30	Execution timed out	2075 ms	264964 KB	Time limit exceeded
31	Execution timed out	2032 ms	264964 KB	Time limit exceeded
32	Execution timed out	2064 ms	291328 KB	Time limit exceeded

답안 #78598

Compilation message

Subtask #1 25.0 / 30.0

Subtask #2 30.625 / 70.0

Subtask #1
25.0 / 30.0

Subtask #2
30.625 / 70.0