oj.uz

답안 #961996

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961996 2024-04-13T02:21:25 Z pcc Tracks in the Snow (BOI13_tracks) C++17
60.625 / 100
 2000 ms 102212 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define tiii tuple<int,int,int>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

const int mxn = 4040;
int N,M;
string arr[mxn];
int dist[mxn][mxn];
deque<tiii> dq;
pii dir[] = {{0,1},{0,-1},{1,0},{-1,0}};

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(dist,-1,sizeof(dist));
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		cin>>arr[i];
		arr[i] = "."+arr[i]+".";
	}
	arr[0] = arr[N+1] = string(M+2,'.');
	dist[1][1] = 1;
	dq.push_back(tiii(1,1,1));
	while(!dq.empty()){
		auto [r,c,d] = dq.front();
		dq.pop_front();
		if(dist[r][c] != d)continue;
		for(auto &dd:dir){
			int nr = r+dd.fs,nc = c+dd.sc;
			if(arr[nr][nc] == '.')continue;
			int nd = d+(arr[nr][nc] != arr[r][c]);
			if(dist[nr][nc] == -1||dist[nr][nc]>nd){
				dist[nr][nc] = nd;
				if(nd == d)dq.push_back(tiii(nr,nc,dist[nr][nc]));
				else dq.push_front(tiii(nr,nc,dist[nr][nc]));
			}
		}
	}
	int ans = 0;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)ans = max(ans,dist[i][j]);
	}
	cout<<ans<<'\n';
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1589 ms 66384 KB Output is correct
2 Correct 9 ms 64348 KB Output is correct
3 Correct 9 ms 64348 KB Output is correct
4 Correct 311 ms 65312 KB Output is correct
5 Correct 76 ms 64680 KB Output is correct
6 Correct 10 ms 64344 KB Output is correct
7 Correct 9 ms 64348 KB Output is correct
8 Correct 11 ms 64344 KB Output is correct
9 Correct 9 ms 64348 KB Output is correct
10 Correct 58 ms 64848 KB Output is correct
11 Correct 45 ms 64600 KB Output is correct
12 Correct 325 ms 65108 KB Output is correct
13 Correct 75 ms 64676 KB Output is correct
14 Correct 70 ms 64676 KB Output is correct
15 Correct 1206 ms 65720 KB Output is correct
16 Correct 1588 ms 66468 KB Output is correct
17 Correct 666 ms 65316 KB Output is correct
18 Correct 304 ms 65104 KB Output is correct

Subtask #2
30.625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 64348 KB Output is correct
2 Execution timed out 2057 ms 68340 KB Time limit exceeded
3 Execution timed out 2013 ms 96124 KB Time limit exceeded
4 Execution timed out 2063 ms 73528 KB Time limit exceeded
5 Correct 75 ms 82152 KB Output is correct
6 Execution timed out 2062 ms 101904 KB Time limit exceeded
7 Correct 10 ms 64348 KB Output is correct
8 Correct 9 ms 64348 KB Output is correct
9 Correct 483 ms 64668 KB Output is correct
10 Correct 9 ms 64348 KB Output is correct
11 Correct 10 ms 64344 KB Output is correct
12 Correct 9 ms 64348 KB Output is correct
13 Execution timed out 2064 ms 68300 KB Time limit exceeded
14 Execution timed out 2051 ms 66824 KB Time limit exceeded
15 Correct 23 ms 66472 KB Output is correct
16 Execution timed out 2061 ms 66648 KB Time limit exceeded
17 Execution timed out 2067 ms 73740 KB Time limit exceeded
18 Correct 54 ms 72280 KB Output is correct
19 Execution timed out 2064 ms 73164 KB Time limit exceeded
20 Execution timed out 2029 ms 71520 KB Time limit exceeded
21 Execution timed out 2028 ms 83024 KB Time limit exceeded
22 Correct 73 ms 82152 KB Output is correct
23 Execution timed out 2035 ms 81548 KB Time limit exceeded
24 Correct 78 ms 82256 KB Output is correct
25 Correct 307 ms 96076 KB Output is correct
26 Correct 450 ms 88544 KB Output is correct
27 Execution timed out 2062 ms 99136 KB Time limit exceeded
28 Execution timed out 2041 ms 101756 KB Time limit exceeded
29 Execution timed out 2051 ms 100496 KB Time limit exceeded
30 Execution timed out 2033 ms 100224 KB Time limit exceeded
31 Execution timed out 2007 ms 97048 KB Time limit exceeded
32 Execution timed out 2073 ms 102212 KB Time limit exceeded