Submission #888487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888487	2023-12-17T14:22:16 Z	bashNewbie	Tracks in the Snow (BOI13_tracks)	C++17	100 / 100	570 ms	86004 KB

tracks

#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

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

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