oj.uz

답안 #888475

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
888475 2023-12-17T14:01:30 Z bashNewbie Tracks in the Snow (BOI13_tracks) C++17
69.375 / 100
 2000 ms 307264 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

vi& operator+=(vi& lhs, const vi& rhs) {
	int n = lhs.size();
	for(int i = 0; i < n; i++) lhs[i] += rhs[i];
	return lhs;
}
vi operator+(vi lhs, const vi& rhs) {
	lhs += rhs;
	return lhs;
}

int main() {
	fast_io;

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

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

	auto in = [&] (vi v) {
		return -1 < v[0] && v[0] < n && -1 < v[1] && v[1] < m;
	};
	auto f = [&] (vi v) {
		return s[v[0]][v[1]];
	};
	auto g = [&] (vi v) {
		return v[0]*m+v[1];
	};
	auto bad = [&] (vi v) {
		return f(v) == '.';
	};
	auto same = [&] (vi v, vi w) {
		return f(v) == f(w);
	};

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

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 201 ms 2388 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 113 ms 5284 KB Output is correct
5 Correct 24 ms 860 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 30 ms 604 KB Output is correct
11 Correct 30 ms 1624 KB Output is correct
12 Correct 71 ms 1200 KB Output is correct
13 Correct 18 ms 860 KB Output is correct
14 Correct 18 ms 860 KB Output is correct
15 Correct 148 ms 2004 KB Output is correct
16 Correct 190 ms 2576 KB Output is correct
17 Correct 96 ms 1624 KB Output is correct
18 Correct 120 ms 5212 KB Output is correct

Subtask #2
39.375 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 860 KB Output is correct
2 Correct 565 ms 8284 KB Output is correct
3 Execution timed out 2039 ms 81236 KB Time limit exceeded
4 Correct 548 ms 19292 KB Output is correct
5 Execution timed out 2028 ms 45656 KB Time limit exceeded
6 Execution timed out 2061 ms 239544 KB Time limit exceeded
7 Correct 11 ms 860 KB Output is correct
8 Correct 13 ms 860 KB Output is correct
9 Correct 24 ms 984 KB Output is correct
10 Correct 8 ms 604 KB Output is correct
11 Correct 7 ms 860 KB Output is correct
12 Correct 10 ms 348 KB Output is correct
13 Correct 608 ms 8284 KB Output is correct
14 Correct 356 ms 4956 KB Output is correct
15 Correct 246 ms 5464 KB Output is correct
16 Correct 336 ms 3928 KB Output is correct
17 Correct 1522 ms 20828 KB Output is correct
18 Correct 1006 ms 20568 KB Output is correct
19 Correct 532 ms 19292 KB Output is correct
20 Correct 774 ms 17820 KB Output is correct
21 Correct 1952 ms 47184 KB Output is correct
22 Execution timed out 2045 ms 45656 KB Time limit exceeded
23 Execution timed out 2064 ms 39772 KB Time limit exceeded
24 Execution timed out 2009 ms 46168 KB Time limit exceeded
25 Execution timed out 2060 ms 81060 KB Time limit exceeded
26 Execution timed out 2070 ms 303420 KB Time limit exceeded
27 Execution timed out 2043 ms 307264 KB Time limit exceeded
28 Execution timed out 2050 ms 239364 KB Time limit exceeded
29 Execution timed out 2027 ms 267860 KB Time limit exceeded
30 Execution timed out 2041 ms 285236 KB Time limit exceeded
31 Execution timed out 2060 ms 57296 KB Time limit exceeded
32 Execution timed out 2049 ms 299416 KB Time limit exceeded