oj.uz

답안 #481111

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481111 2021-10-19T13:43:28 Z dolamanee Tracks in the Snow (BOI13_tracks) C++17
100 / 100
 1580 ms 163496 KB 
// Created by ...
#include <bits/stdc++.h>

#define vll vector< ll >
#define M 100000
#define MD 1000000007
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pii pair<ll,ll>
#define vec(a) vector<a >
#define all(a) (a).begin(),(a).end()
#define se second
#define fi first
#define inf 0xffffffff
#define int long long
#define endl '\n'
#define rep(i,a,b) for(ll i=a;i<=b;++i)
#define per(i,b,a) for(ll i=b;i>=a;--i)
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define EACH(x, a) auto _Itr=begin(a);for (auto x=*_Itr;_Itr!=end(a);_Itr=next(_Itr),x=*_Itr)

using namespace std;
using ll = long long;
using ld = long double;
ll md = MD;

template<class... Args> auto Vec(size_t n, Args&&... args) {
	if constexpr(sizeof...(args) == 1)return vector(n, args...);
	else return vector(n, Vec(args...));
}
template<class T, class... Args> void DBS(T t, Args... args) {
	cerr << t;
	if constexpr(sizeof...(args) == 0) cerr << "]\n";
	else cerr << ", ", DBS(args...);
}
#ifdef _DEBUG
#define db(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBS(__VA_ARGS__)
#else
#define db(...) 0
#endif

ll exp(ll a, ll b) {ll r = 1ll; while (b > 0) {if (b & 1) {r = r * (a % md); r = (r + md) % md;} b >>= 1; a = (a % md) * (a % md); a = (a + md) % md;} return (r + md) % md;}
ll gcd(ll a, ll b) {if (b == 0)return a; return gcd(b, a % b);}
template<class T> T Min(T a, T b) {if (a < b)return a; return b;}
template<class T> T Max(T a, T b) {if (a > b)return a; return b;}
const int Mx = 4005;
char grid[Mx][Mx];
int h, w, vis[Mx][Mx];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void solve() {
	cin >> h >> w;
	rep(i, 0, h - 1)rep(j, 0, w - 1)cin >> grid[i][j];
	queue<pii> q[2];
	char curr = grid[0][0];
	int id = (curr == 'F' ? 0 : 1), ans = 1;
	q[id].push({0, 0});
	while (!q[0].empty() || !q[1].empty()) {
		if (q[id].empty()) {
			++ans;
			id ^= 1;
			if (curr == 'F')curr = 'R';
			else curr = 'F';
		}
		while (!q[id].empty()) {
			auto [x, y] = q[id].front(); q[id].pop();
			vis[x][y] = 1;
			for (int i = 0; i < 4; ++i) {
				int nx = x + dx[i], ny = y + dy[i];
				if (nx < 0 || ny < 0 || nx >= h || ny >= w || vis[nx][ny] || grid[nx][ny] == '.')continue;
				vis[nx][ny] = 1;
				if (grid[nx][ny] == curr)q[id].push({nx, ny});
				else q[id ^ 1].push({nx, ny});
			}
		}
	}
	cout << ans;
}

int32_t main() {
	IOS;

	int t = 1;
	//cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 6348 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 13 ms 5760 KB Output is correct
5 Correct 5 ms 3148 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 844 KB Output is correct
9 Correct 2 ms 1100 KB Output is correct
10 Correct 5 ms 2636 KB Output is correct
11 Correct 4 ms 2252 KB Output is correct
12 Correct 7 ms 3404 KB Output is correct
13 Correct 4 ms 3148 KB Output is correct
14 Correct 4 ms 3148 KB Output is correct
15 Correct 18 ms 6088 KB Output is correct
16 Correct 20 ms 6356 KB Output is correct
17 Correct 20 ms 6096 KB Output is correct
18 Correct 12 ms 5784 KB Output is correct

Subtask #2
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 31052 KB Output is correct
2 Correct 91 ms 18180 KB Output is correct
3 Correct 441 ms 77352 KB Output is correct
4 Correct 158 ms 44612 KB Output is correct
5 Correct 311 ms 64204 KB Output is correct
6 Correct 1490 ms 163496 KB Output is correct
7 Correct 19 ms 32332 KB Output is correct
8 Correct 21 ms 30984 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 21 ms 31776 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Correct 86 ms 18244 KB Output is correct
14 Correct 51 ms 12356 KB Output is correct
15 Correct 44 ms 17008 KB Output is correct
16 Correct 34 ms 7232 KB Output is correct
17 Correct 223 ms 34156 KB Output is correct
18 Correct 173 ms 49240 KB Output is correct
19 Correct 147 ms 44612 KB Output is correct
20 Correct 108 ms 28780 KB Output is correct
21 Correct 266 ms 55816 KB Output is correct
22 Correct 312 ms 64264 KB Output is correct
23 Correct 412 ms 51696 KB Output is correct
24 Correct 270 ms 54612 KB Output is correct
25 Correct 751 ms 143172 KB Output is correct
26 Correct 909 ms 125648 KB Output is correct
27 Correct 1081 ms 146500 KB Output is correct
28 Correct 1580 ms 163372 KB Output is correct
29 Correct 1395 ms 160520 KB Output is correct
30 Correct 1224 ms 160688 KB Output is correct
31 Correct 989 ms 113244 KB Output is correct
32 Correct 1075 ms 149532 KB Output is correct