oj.uz

답안 #481109

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
481109 2021-10-19T13:40:11 Z dolamanee Tracks in the Snow (BOI13_tracks) C++17
31.25 / 100
 2000 ms 1048580 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;
				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
5.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2112 ms 1048580 KB Time limit exceeded
2 Correct 1 ms 460 KB Output is correct
3 Execution timed out 2106 ms 441756 KB Time limit exceeded
4 Execution timed out 2138 ms 945120 KB Time limit exceeded
5 Execution timed out 2134 ms 933424 KB Time limit exceeded
6 Correct 1 ms 460 KB Output is correct
7 Execution timed out 2100 ms 441808 KB Time limit exceeded
8 Runtime error 1907 ms 1048580 KB Execution killed with signal 9
9 Correct 51 ms 2116 KB Output is correct
10 Execution timed out 2147 ms 912220 KB Time limit exceeded
11 Execution timed out 2150 ms 940228 KB Time limit exceeded
12 Runtime error 1997 ms 1048580 KB Execution killed with signal 9
13 Execution timed out 2152 ms 912940 KB Time limit exceeded
14 Execution timed out 2144 ms 915548 KB Time limit exceeded
15 Execution timed out 2141 ms 1022304 KB Time limit exceeded
16 Runtime error 1930 ms 1048580 KB Execution killed with signal 9
17 Execution timed out 2152 ms 1003420 KB Time limit exceeded
18 Execution timed out 2142 ms 982096 KB Time limit exceeded

Subtask #2
26.25 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 31052 KB Output is correct
2 Execution timed out 2122 ms 731856 KB Time limit exceeded
3 Execution timed out 2073 ms 446628 KB Time limit exceeded
4 Execution timed out 2102 ms 411892 KB Time limit exceeded
5 Correct 303 ms 68876 KB Output is correct
6 Execution timed out 2136 ms 958140 KB Time limit exceeded
7 Correct 20 ms 32332 KB Output is correct
8 Correct 19 ms 31028 KB Output is correct
9 Execution timed out 2102 ms 540088 KB Time limit exceeded
10 Correct 1 ms 460 KB Output is correct
11 Correct 21 ms 31788 KB Output is correct
12 Correct 2 ms 1612 KB Output is correct
13 Execution timed out 2116 ms 715620 KB Time limit exceeded
14 Execution timed out 2151 ms 996372 KB Time limit exceeded
15 Correct 42 ms 16964 KB Output is correct
16 Execution timed out 2124 ms 715128 KB Time limit exceeded
17 Execution timed out 2106 ms 528520 KB Time limit exceeded
18 Correct 173 ms 51272 KB Output is correct
19 Execution timed out 2090 ms 411412 KB Time limit exceeded
20 Execution timed out 2094 ms 310000 KB Time limit exceeded
21 Execution timed out 2106 ms 339952 KB Time limit exceeded
22 Correct 314 ms 69056 KB Output is correct
23 Execution timed out 2117 ms 570276 KB Time limit exceeded
24 Correct 283 ms 59316 KB Output is correct
25 Correct 741 ms 147952 KB Output is correct
26 Execution timed out 2134 ms 906416 KB Time limit exceeded
27 Execution timed out 2138 ms 896904 KB Time limit exceeded
28 Execution timed out 2145 ms 958884 KB Time limit exceeded
29 Execution timed out 2142 ms 918668 KB Time limit exceeded
30 Execution timed out 2059 ms 1048580 KB Time limit exceeded
31 Execution timed out 2075 ms 1048580 KB Time limit exceeded
32 Runtime error 1941 ms 1048580 KB Execution killed with signal 9