oj.uz

답안 #715545

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715545 2023-03-27T07:52:35 Z jackpost Tracks in the Snow (BOI13_tracks) C++14
100 / 100
 1641 ms 143264 KB 
// IN THE NAME OF GOD
#include<bits/stdc++.h>
#define endl '\n'
#define file_reading freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define flush cout.flush();
using namespace std;
typedef long long ll;
typedef long double dll;
typedef unsigned long long ull;
 
const int N = 4e3+5; 
int dat[N][N], mark[N][N], ans, having, must; 
queue<pair<int,int>> q,qq; 
 
void bfs(int n, int m){
	q.push({n,m}); 
	int x,y; 
	int tim = 0; 
	while(having != must){
		ans++;
		tim++;
		if (tim&1){
			while(q.size()){
				x = q.front().first;
				y = q.front().second; 
				q.pop(); 
				if (mark[x][y]) continue;	
				mark[x][y] = 1; 
				having++; 
				if (x > 1 && dat[x][y] == dat[x-1][y] && !mark[x-1][y]) q.push({x-1,y});
				if (x < n && dat[x][y] == dat[x+1][y] && !mark[x+1][y]) q.push({x+1,y});
				if (y > 1 && dat[x][y] == dat[x][y-1] && !mark[x][y-1]) q.push({x,y-1});
				if (y < m && dat[x][y] == dat[x][y+1] && !mark[x][y+1]) q.push({x,y+1});
				if (x > 1 && dat[x][y] != dat[x-1][y] && !mark[x-1][y] && dat[x][y] + dat[x-1][y] == 3) qq.push({x-1,y});
				if (x < n && dat[x][y] != dat[x+1][y] && !mark[x+1][y] && dat[x][y] + dat[x+1][y] == 3) qq.push({x+1,y});
				if (y > 1 && dat[x][y] != dat[x][y-1] && !mark[x][y-1] && dat[x][y] + dat[x][y-1] == 3) qq.push({x,y-1});
				if (y < m && dat[x][y] != dat[x][y+1] && !mark[x][y+1] && dat[x][y] + dat[x][y+1] == 3) qq.push({x,y+1});
			}
		}
		else{
			while(qq.size()){
				x = qq.front().first;
				y = qq.front().second; 
				qq.pop(); 
				if (mark[x][y]) continue; 
				mark[x][y] = 1; 
				having++; 
				if (x > 1 && dat[x][y] == dat[x-1][y] && !mark[x-1][y]) qq.push({x-1,y});
				if (x < n && dat[x][y] == dat[x+1][y] && !mark[x+1][y]) qq.push({x+1,y});
				if (y > 1 && dat[x][y] == dat[x][y-1] && !mark[x][y-1]) qq.push({x,y-1});
				if (y < m && dat[x][y] == dat[x][y+1] && !mark[x][y+1]) qq.push({x,y+1});
				if (x > 1 && dat[x][y] != dat[x-1][y] && !mark[x-1][y] && dat[x][y] + dat[x-1][y] == 3) q.push({x-1,y});
				if (x < n && dat[x][y] != dat[x+1][y] && !mark[x+1][y] && dat[x][y] + dat[x+1][y] == 3) q.push({x+1,y});
				if (y > 1 && dat[x][y] != dat[x][y-1] && !mark[x][y-1] && dat[x][y] + dat[x][y-1] == 3) q.push({x,y-1});
				if (y < m && dat[x][y] != dat[x][y+1] && !mark[x][y+1] && dat[x][y] + dat[x][y+1] == 3) q.push({x,y+1});
			}
		}
	}
}
 
void solve(){  
	int n,m; cin >> n >> m; 
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			char g; cin >> g; 
			if (g == '.') dat[i][j] = 0; 
			else if (g == 'R') dat[i][j] = 1, must++; 
			else dat[i][j] = 2, must++; 
		}
	}
	bfs(n,m); 
	cout << ans << endl; 
}
 
int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t; t=1; //cin >> t;
	while(t--){solve();}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 6228 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 14 ms 5724 KB Output is correct
5 Correct 6 ms 3156 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 1108 KB Output is correct
10 Correct 6 ms 2752 KB Output is correct
11 Correct 6 ms 2260 KB Output is correct
12 Correct 13 ms 3312 KB Output is correct
13 Correct 5 ms 3156 KB Output is correct
14 Correct 5 ms 3156 KB Output is correct
15 Correct 21 ms 6100 KB Output is correct
16 Correct 25 ms 6220 KB Output is correct
17 Correct 17 ms 5960 KB Output is correct
18 Correct 15 ms 5712 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 31412 KB Output is correct
2 Correct 89 ms 19700 KB Output is correct
3 Correct 464 ms 104684 KB Output is correct
4 Correct 148 ms 43836 KB Output is correct
5 Correct 253 ms 79904 KB Output is correct
6 Correct 1620 ms 143244 KB Output is correct
7 Correct 18 ms 32724 KB Output is correct
8 Correct 20 ms 31444 KB Output is correct
9 Correct 4 ms 724 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 20 ms 32188 KB Output is correct
12 Correct 2 ms 1620 KB Output is correct
13 Correct 83 ms 19728 KB Output is correct
14 Correct 48 ms 13180 KB Output is correct
15 Correct 38 ms 16104 KB Output is correct
16 Correct 41 ms 7684 KB Output is correct
17 Correct 218 ms 40972 KB Output is correct
18 Correct 140 ms 47560 KB Output is correct
19 Correct 130 ms 43900 KB Output is correct
20 Correct 129 ms 35796 KB Output is correct
21 Correct 276 ms 79820 KB Output is correct
22 Correct 246 ms 79836 KB Output is correct
23 Correct 424 ms 65660 KB Output is correct
24 Correct 250 ms 76704 KB Output is correct
25 Correct 614 ms 125720 KB Output is correct
26 Correct 825 ms 110156 KB Output is correct
27 Correct 1118 ms 128984 KB Output is correct
28 Correct 1641 ms 143264 KB Output is correct
29 Correct 1531 ms 139468 KB Output is correct
30 Correct 1338 ms 136576 KB Output is correct
31 Correct 1297 ms 101708 KB Output is correct
32 Correct 927 ms 127840 KB Output is correct