답안 #888471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888471	2023-12-17T13:48:07 Z	bashNewbie	Tracks in the Snow (BOI13_tracks)	C++17	75.8333 / 100	1031 ms	140720 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 main() {
	fast_io;

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

	auto in = [&] (int x) {
		return -1 < x && x < n*m;
	};
	auto bad = [&] (int x) {
		return s[x/m][x%m] == '.';
	};
	auto same = [&] (int x, int y) {
		int xr = x/m, xc = x%m, yr = y/m, yc = y%m;
		return s[xr][xc] == s[yr][yc];
	};

	queue<int> q, nq; vi vis(n*m), adj = {-m, -1, 1, m}; int ret = 0;
	q.push(0), vis[0] = 1;
	while(!q.empty()) {
		ret++;
		while(!q.empty()) {
			int x = q.front(); q.pop(), nq.push(x);
			for(int c: adj) {
				int y = x+c;
				if(!in(y) || vis[y] || bad(y) || !same(x, y)) continue;
				q.push(y), vis[y] = 1;
			}
		}
		while(!nq.empty()) {
			int x = nq.front(); nq.pop();
			for(int c: adj) {
				int y = x+c;
				if(!in(y) || vis[y] || bad(y)) continue;
				q.push(y), vis[y] = 1;
			}
		}
	}
	cout << ret << "\n";
}

Subtask #1

23.3333333333 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	13 ms	1884 KB	Output isn't correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	6 ms	1628 KB	Output is correct
5	Correct	2 ms	860 KB	Output is correct
6	Correct	0 ms	344 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Incorrect	1 ms	348 KB	Output isn't correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	2 ms	860 KB	Output is correct
11	Correct	2 ms	640 KB	Output is correct
12	Incorrect	5 ms	860 KB	Output isn't correct
13	Correct	2 ms	860 KB	Output is correct
14	Correct	2 ms	860 KB	Output is correct
15	Correct	12 ms	1884 KB	Output is correct
16	Incorrect	13 ms	1880 KB	Output isn't correct
17	Correct	10 ms	1884 KB	Output is correct
18	Correct	6 ms	1628 KB	Output is correct

Subtask #2

52.5 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	860 KB	Output isn't correct
2	Correct	51 ms	9204 KB	Output is correct
3	Correct	245 ms	88844 KB	Output is correct
4	Correct	59 ms	21084 KB	Output is correct
5	Incorrect	314 ms	49892 KB	Output isn't correct
6	Correct	1031 ms	119788 KB	Output is correct
7	Incorrect	1 ms	604 KB	Output isn't correct
8	Incorrect	1 ms	860 KB	Output isn't correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	1 ms	856 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	50 ms	9072 KB	Output is correct
14	Correct	29 ms	5724 KB	Output is correct
15	Correct	18 ms	6236 KB	Output is correct
16	Correct	25 ms	4184 KB	Output is correct
17	Correct	130 ms	22744 KB	Output is correct
18	Correct	59 ms	22664 KB	Output is correct
19	Correct	59 ms	20956 KB	Output is correct
20	Correct	58 ms	19540 KB	Output is correct
21	Correct	144 ms	51792 KB	Output is correct
22	Incorrect	312 ms	49928 KB	Output isn't correct
23	Correct	278 ms	43092 KB	Output is correct
24	Incorrect	167 ms	50268 KB	Output isn't correct
25	Correct	311 ms	88916 KB	Output is correct
26	Correct	477 ms	118128 KB	Output is correct
27	Correct	603 ms	133340 KB	Output is correct
28	Correct	967 ms	119768 KB	Output is correct
29	Incorrect	958 ms	119228 KB	Output isn't correct
30	Correct	800 ms	127068 KB	Output is correct
31	Incorrect	684 ms	57424 KB	Output isn't correct
32	Correct	540 ms	140720 KB	Output is correct