oj.uz

답안 #78611

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
78611 2018-10-06T17:08:40 Z bash Tracks in the Snow (BOI13_tracks) C++17
1.66667 / 100
 2000 ms 81940 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;
}
 
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.tie(0);
	cout.tie(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;
}

Subtask #1
1.66666666667 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2054 ms 6388 KB Time limit exceeded
2 Incorrect 2 ms 6388 KB Output isn't correct
3 Incorrect 2 ms 6388 KB Output isn't correct
4 Incorrect 444 ms 6388 KB Output isn't correct
5 Incorrect 97 ms 6388 KB Output isn't correct
6 Incorrect 2 ms 6388 KB Output isn't correct
7 Incorrect 3 ms 6388 KB Output isn't correct
8 Incorrect 4 ms 6388 KB Output isn't correct
9 Incorrect 3 ms 6388 KB Output isn't correct
10 Incorrect 5 ms 6388 KB Output isn't correct
11 Correct 47 ms 6388 KB Output is correct
12 Incorrect 430 ms 6388 KB Output isn't correct
13 Incorrect 99 ms 6388 KB Output isn't correct
14 Incorrect 99 ms 6388 KB Output isn't correct
15 Execution timed out 2047 ms 6388 KB Time limit exceeded
16 Execution timed out 2050 ms 6560 KB Time limit exceeded
17 Incorrect 9 ms 6560 KB Output isn't correct
18 Incorrect 418 ms 6560 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 29948 KB Output isn't correct
2 Incorrect 66 ms 29948 KB Output isn't correct
3 Incorrect 279 ms 78972 KB Output isn't correct
4 Incorrect 78 ms 78972 KB Output isn't correct
5 Incorrect 304 ms 78972 KB Output isn't correct
6 Execution timed out 2082 ms 81624 KB Time limit exceeded
7 Incorrect 27 ms 81624 KB Output isn't correct
8 Incorrect 26 ms 81624 KB Output isn't correct
9 Incorrect 3 ms 81624 KB Output isn't correct
10 Incorrect 3 ms 81624 KB Output isn't correct
11 Incorrect 25 ms 81624 KB Output isn't correct
12 Incorrect 12 ms 81624 KB Output isn't correct
13 Incorrect 67 ms 81624 KB Output isn't correct
14 Incorrect 22 ms 81624 KB Output isn't correct
15 Incorrect 25 ms 81624 KB Output isn't correct
16 Incorrect 19 ms 81624 KB Output isn't correct
17 Incorrect 76 ms 81624 KB Output isn't correct
18 Incorrect 87 ms 81624 KB Output isn't correct
19 Incorrect 83 ms 81624 KB Output isn't correct
20 Incorrect 72 ms 81624 KB Output isn't correct
21 Incorrect 171 ms 81624 KB Output isn't correct
22 Incorrect 290 ms 81624 KB Output isn't correct
23 Incorrect 147 ms 81624 KB Output isn't correct
24 Incorrect 174 ms 81624 KB Output isn't correct
25 Incorrect 301 ms 81624 KB Output isn't correct
26 Incorrect 733 ms 81624 KB Output isn't correct
27 Execution timed out 2062 ms 81624 KB Time limit exceeded
28 Execution timed out 2060 ms 81624 KB Time limit exceeded
29 Execution timed out 2078 ms 81624 KB Time limit exceeded
30 Execution timed out 2076 ms 81624 KB Time limit exceeded
31 Execution timed out 2087 ms 81624 KB Time limit exceeded
32 Execution timed out 2074 ms 81940 KB Time limit exceeded