oj.uz

답안 #888487

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888487 2023-12-17T14:22:16 Z bashNewbie Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 570 ms 86004 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

#define fast_io ios::sync_with_stdio(0), cin.tie(0)
#define vi vector<int>
#define vvi vector<vi>
#define vs vector<string>
#define pb push_back

int n, m;
vs s; vi vis;
queue<int> q, nq;

inline bool in(int x) {
	return -1 < x && x < n*m;
}
inline bool bad(int x) {
	return s[x/m][x%m] == '.';
}
inline bool same(int x, int y) {
	return s[x/m][x%m] == s[y/m][y%m];
}
inline void put(int x, int y) {
	if(same(x, y)) q.push(y); else
	nq.push(y);
	vis[y] = 1;
}

int main() {
	fast_io;

	vvi adj = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

	cin >> n >> m;
	s = vs(n); for(auto &t: s) cin >> t;

	vis = vi(n*m); int ret = 0;
	q.push(0), vis[0] = 1;
	while(!q.empty()) {
		ret++; vi add;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			if(x%m > 0 && !vis[x-1] && !bad(x-1)) put(x, x-1);
			if(x%m<m-1 && !vis[x+1] && !bad(x+1)) put(x, x+1);
			if(x/m > 0 && !vis[x-m] && !bad(x-m)) put(x, x-m);
			if(x/m<n-1 && !vis[x+m] && !bad(x+m)) put(x, x+m);
		}
		while(!nq.empty()) {
			int x = nq.front(); nq.pop(), q.push(x);
		}
	}
	cout << ret << "\n";
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 1628 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 3 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 7 ms 1628 KB Output is correct
16 Correct 8 ms 1628 KB Output is correct
17 Correct 6 ms 1628 KB Output is correct
18 Correct 4 ms 1116 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 28 ms 8212 KB Output is correct
3 Correct 162 ms 80728 KB Output is correct
4 Correct 38 ms 19032 KB Output is correct
5 Correct 147 ms 45404 KB Output is correct
6 Correct 569 ms 86004 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 29 ms 8028 KB Output is correct
14 Correct 19 ms 4956 KB Output is correct
15 Correct 13 ms 5212 KB Output is correct
16 Correct 14 ms 3676 KB Output is correct
17 Correct 77 ms 20572 KB Output is correct
18 Correct 49 ms 20328 KB Output is correct
19 Correct 38 ms 19036 KB Output is correct
20 Correct 38 ms 17500 KB Output is correct
21 Correct 98 ms 46936 KB Output is correct
22 Correct 146 ms 45400 KB Output is correct
23 Correct 152 ms 39000 KB Output is correct
24 Correct 117 ms 45912 KB Output is correct
25 Correct 258 ms 80724 KB Output is correct
26 Correct 261 ms 61788 KB Output is correct
27 Correct 377 ms 81748 KB Output is correct
28 Correct 570 ms 85844 KB Output is correct
29 Correct 549 ms 85336 KB Output is correct
30 Correct 489 ms 83508 KB Output is correct
31 Correct 382 ms 51976 KB Output is correct
32 Correct 373 ms 81500 KB Output is correct