Submission #377156

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
377156	2021-03-13T04:57:53 Z	pavement	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	920 ms	128420 KB

tracks

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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