oj.uz

답안 #377156

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
377156 2021-03-13T04:57:53 Z pavement Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 920 ms 128420 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int H, W, ans, dr[] = {-1, 0, 0, 1}, dc[] = {0, -1, 1, 0};
char tmp, prv, F[4005][4005];
bool vis[4005][4005];
deque<ii> Q;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> H >> W;
	for (int i = 1; i <= H; i++)
		for (int j = 1; j <= W; j++) {
			cin >> tmp;
			if (tmp == '.') tmp = 2;
			else if (tmp == 'R') tmp = 0;
			else tmp = 1;
			F[i][j] = tmp;
		}
	Q.eb(1, 1);
	prv = F[1][1];
	while (!Q.empty()) {
		auto [r, c] = Q.front();
		Q.pop_front();
		if (vis[r][c]) continue;
		vis[r][c] = 1;
		if (F[r][c] != prv) ans++;
		prv = F[r][c];
		for (int k = 0; k < 4; k++) {
			int nr = r + dr[k], nc = c + dc[k];
			if (1 <= nr && nr <= H && 1 <= nc && nc <= W && F[nr][nc] != 2 && !vis[nr][nc]) {
				if (F[nr][nc] != F[r][c]) Q.eb(nr, nc);
				else Q.emplace_front(nr, nc);
			}
		}
	}
	cout << ++ans << '\n';
}

Compilation message

tracks.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   33 | main() {
      |      ^

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 4352 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 764 KB Output is correct
4 Correct 11 ms 4588 KB Output is correct
5 Correct 5 ms 2668 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 876 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 1132 KB Output is correct
10 Correct 4 ms 2284 KB Output is correct
11 Correct 3 ms 2028 KB Output is correct
12 Correct 8 ms 2668 KB Output is correct
13 Correct 5 ms 2688 KB Output is correct
14 Correct 5 ms 2668 KB Output is correct
15 Correct 17 ms 4332 KB Output is correct
16 Correct 20 ms 4332 KB Output is correct
17 Correct 14 ms 4076 KB Output is correct
18 Correct 12 ms 4716 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 30336 KB Output is correct
2 Correct 70 ms 10220 KB Output is correct
3 Correct 435 ms 31724 KB Output is correct
4 Correct 122 ms 15104 KB Output is correct
5 Correct 250 ms 23808 KB Output is correct
6 Correct 920 ms 60356 KB Output is correct
7 Correct 22 ms 31724 KB Output is correct
8 Correct 21 ms 30316 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 21 ms 31084 KB Output is correct
12 Correct 2 ms 1516 KB Output is correct
13 Correct 70 ms 10220 KB Output is correct
14 Correct 41 ms 7532 KB Output is correct
15 Correct 40 ms 8172 KB Output is correct
16 Correct 32 ms 3564 KB Output is correct
17 Correct 180 ms 16364 KB Output is correct
18 Correct 139 ms 16128 KB Output is correct
19 Correct 125 ms 15084 KB Output is correct
20 Correct 104 ms 14060 KB Output is correct
21 Correct 257 ms 24812 KB Output is correct
22 Correct 235 ms 24080 KB Output is correct
23 Correct 334 ms 20076 KB Output is correct
24 Correct 249 ms 24940 KB Output is correct
25 Correct 606 ms 31704 KB Output is correct
26 Correct 525 ms 128420 KB Output is correct
27 Correct 736 ms 114520 KB Output is correct
28 Correct 890 ms 60160 KB Output is correct
29 Correct 894 ms 52788 KB Output is correct
30 Correct 811 ms 67604 KB Output is correct
31 Correct 798 ms 26604 KB Output is correct
32 Correct 661 ms 78584 KB Output is correct