답안 #78608

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
78608	2018-10-06T16:51:45 Z	bash	Tracks in the Snow (BOI13_tracks)	C++17	57.2917 / 100	2000 ms	80972 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 = 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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