oj.uz

답안 #1039567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1039567 2024-07-31T04:37:26 Z 박영우(#11029) Toy (CEOI24_toy) C++17
0 / 100
 96 ms 197056 KB 
//#define LOCAL
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<short, short> pss;
#define MAX 2020
#define MAXS 20
#define INF 1'000'000'010'000'000'000
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define TC 0
#ifdef LOCAL
#define DEBUG(a) cout<<a
#else
#define DEBUG(...) 
#endif
int mp[MAX][MAX];
int chkh[MAX][MAX];
int chkv[MAX][MAX];
int dpu[MAX][MAX];
int dpd[MAX][MAX];
int dpl[MAX][MAX];
int dpr[MAX][MAX];
vector<int> adj[MAX * MAX];
int vis[MAX];
void dfs(int x) {
	vis[x] = 1;
	for (auto v : adj[x]) if (!vis[v]) dfs(v);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, M, K, L;
	cin >> N >> M >> K >> L;
	swap(N, M);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	swap(a, b);
	swap(c, d);
	a++;
	d++;
	int x, y;
	x = a;
	y = d;
	int i, j;
	string s;
	int gx, gy;
	for (i = 1; i <= N; i++) {
		cin >> s;
		for (j = 1; j <= M; j++) {
			mp[i][j] = 1;
			if (s[j - 1] == 'X') mp[i][j] = 0;
			if (s[j - 1] == '*') {
				gx = i;
				gy = j;
			}
		}
	}
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (mp[i][j]) {
				dpu[i][j] = dpu[i - 1][j] + 1;
				dpl[i][j] = dpl[i][j - 1] + 1;
			}
		}
	}
	for (i = N; i > 0; i--) {
		for (j = M; j > 0; j--) {
			if (mp[i][j]) {
				dpd[i][j] = dpd[i + 1][j] + 1;
				dpr[i][j] = dpr[i][j + 1] + 1;
			}
		}
	}
	for (i = N; i > 0; i--) {
		for (j = M; j > 0; j--) {
			if (dpu[i][j] + dpd[i][j] - 1 < L) mp[i][j] = 0;
			if (dpl[i][j] + dpr[i][j] - 1 < K) mp[i][j] = 0;
		}
	}
	auto get = [&](int x, int y) { return (x - 1) * M + y; };
	auto add = [&](int a, int b) {
		adj[a].push_back(b);
		adj[b].push_back(a);
	};
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) DEBUG(mp[i][j] << bb);
		DEBUG(ln);
	}
	for (i = 1; i <= N; i++) {
		for (j = 1; j <= M; j++) {
			if (mp[i][j] && mp[i][j + 1]) {
				int um = min(dpu[i][j], dpu[i][j + 1]);
				int dm = min(dpd[i][j], dpd[i][j + 1]);
				if (um + dm - 1 >= L) add(get(i, j), get(i, j + 1));
			}
			if (mp[i][j] && mp[i + 1][j]) {
				int lm = min(dpl[i][j], dpl[i + 1][j]);
				int rm = min(dpr[i][j], dpr[i + 1][j]);
				if (lm + rm - 1 >= K) add(get(i, j), get(i + 1, j));
			}
		}
	}
	dfs(get(x, y));
	if (vis[get(gx, gy)]) cout << "YES";
	else cout << "NO";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:113:13: warning: 'gy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |  if (vis[get(gx, gy)]) cout << "YES";
      |          ~~~^~~~~~~~
Main.cpp:113:13: warning: 'gx' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 96336 KB Output is correct
2 Correct 33 ms 96348 KB Output is correct

Subtask #1
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 96336 KB Output is correct
2 Correct 33 ms 96348 KB Output is correct
3 Correct 31 ms 96604 KB Output is correct
4 Runtime error 96 ms 197056 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 96336 KB Output is correct
2 Correct 33 ms 96348 KB Output is correct
3 Correct 31 ms 96604 KB Output is correct
4 Runtime error 96 ms 197056 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 96336 KB Output is correct
2 Correct 33 ms 96348 KB Output is correct
3 Incorrect 33 ms 96852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 96336 KB Output is correct
2 Correct 33 ms 96348 KB Output is correct
3 Correct 31 ms 96604 KB Output is correct
4 Runtime error 96 ms 197056 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 96336 KB Output is correct
2 Correct 33 ms 96348 KB Output is correct
3 Correct 31 ms 96604 KB Output is correct
4 Runtime error 96 ms 197056 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -