oj.uz

답안 #346467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
346467 2021-01-09T20:26:45 Z ahmet Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1242 ms 227452 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ref(a,b,c) for(int (a)=(b);(a)<=(c);++(a))
#define rep(a,b) for(int (a)=0;(a)<(b);++(a))
#define pb push_back
#define mp make_pair
const int mx=5000;
int n,m;
char a[mx][mx];
int depth[mx][mx];
int vis[mx][mx];
int dx[]={-1,1,0,0};
int dy[]={0,0,1,-1};
int check(int x,int y){
	if(x==0 or y==0 or x==n+1 or y==m+1 or a[x][y]=='.' or vis[x][y])return 1;
	else return 0;
}
int ans=1;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin >> a[i][j];
		}
	}
	rep(i,mx)rep(j,mx)depth[i][j]=2e9;
	depth[1][1]=1;
	deque <pair <int,int> > q;
	q.push_front(mp(1,1));
	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop_front();
		if(vis[x][y])continue;
		else vis[x][y]=1;
		//cout << x << " " << y << " " << depth[x][y] << endl;
		//if(x==1 and y==5)cout<<"BURda";
		ans=max(ans,depth[x][y]);
		for(int i=0;i<4;++i){
			int gox=x+dx[i];int goy=y+dy[i];
		//	if(x==1 and y==5)cout<<gox << " " << goy << endl;
			if(check(gox,goy))continue;
			if(a[gox][goy]==a[x][y] and depth[gox][goy]>depth[x][y]){
				depth[gox][goy]=depth[x][y];
				q.push_front(mp(gox,goy));
			//	if(x==1 and y==5)cout<<"BURDa  1 " << i << endl;
			}
			else if(a[gox][goy]!=a[x][y] and depth[gox][goy]>depth[x][y]+1){
				depth[gox][goy]=depth[x][y]+1;
				q.push_back(mp(gox,goy));
				//if(x==1 and y==5)cout<<"BURDa 2  " << i << endl;
			}
		}
	}
	cout << ans << endl;
}

Compilation message

tracks.cpp: In function 'int main()':
tracks.cpp:5:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    5 | #define rep(a,b) for(int (a)=0;(a)<(b);++(a))
      |                          ^
tracks.cpp:28:2: note: in expansion of macro 'rep'
   28 |  rep(i,mx)rep(j,mx)depth[i][j]=2e9;
      |  ^~~
tracks.cpp:5:26: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    5 | #define rep(a,b) for(int (a)=0;(a)<(b);++(a))
      |                          ^
tracks.cpp:28:11: note: in expansion of macro 'rep'
   28 |  rep(i,mx)rep(j,mx)depth[i][j]=2e9;
      |           ^~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 103404 KB Output is correct
2 Correct 58 ms 98412 KB Output is correct
3 Correct 60 ms 98540 KB Output is correct
4 Correct 70 ms 103148 KB Output is correct
5 Correct 61 ms 100844 KB Output is correct
6 Correct 58 ms 98412 KB Output is correct
7 Correct 58 ms 98540 KB Output is correct
8 Correct 58 ms 98668 KB Output is correct
9 Correct 66 ms 99052 KB Output is correct
10 Correct 64 ms 100400 KB Output is correct
11 Correct 62 ms 100076 KB Output is correct
12 Correct 70 ms 101248 KB Output is correct
13 Correct 63 ms 100972 KB Output is correct
14 Correct 62 ms 100844 KB Output is correct
15 Correct 79 ms 103276 KB Output is correct
16 Correct 94 ms 103404 KB Output is correct
17 Correct 77 ms 103148 KB Output is correct
18 Correct 73 ms 103148 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 77 ms 129004 KB Output is correct
2 Correct 137 ms 112620 KB Output is correct
3 Correct 513 ms 162224 KB Output is correct
4 Correct 200 ms 129004 KB Output is correct
5 Correct 354 ms 145516 KB Output is correct
6 Correct 1242 ms 210260 KB Output is correct
7 Correct 78 ms 130540 KB Output is correct
8 Correct 76 ms 129132 KB Output is correct
9 Correct 61 ms 98540 KB Output is correct
10 Correct 59 ms 98284 KB Output is correct
11 Correct 76 ms 129900 KB Output is correct
12 Correct 60 ms 99564 KB Output is correct
13 Correct 139 ms 112620 KB Output is correct
14 Correct 104 ms 108268 KB Output is correct
15 Correct 101 ms 110956 KB Output is correct
16 Correct 95 ms 103532 KB Output is correct
17 Correct 264 ms 124780 KB Output is correct
18 Correct 224 ms 131712 KB Output is correct
19 Correct 197 ms 128876 KB Output is correct
20 Correct 167 ms 121836 KB Output is correct
21 Correct 326 ms 144492 KB Output is correct
22 Correct 343 ms 145516 KB Output is correct
23 Correct 450 ms 136300 KB Output is correct
24 Correct 316 ms 141804 KB Output is correct
25 Correct 813 ms 196076 KB Output is correct
26 Correct 741 ms 227452 KB Output is correct
27 Correct 1004 ms 209532 KB Output is correct
28 Correct 1230 ms 210428 KB Output is correct
29 Correct 1233 ms 208764 KB Output is correct
30 Correct 1100 ms 209784 KB Output is correct
31 Correct 1136 ms 167404 KB Output is correct
32 Correct 874 ms 209888 KB Output is correct