oj.uz

Submission #1039579

# Submission time Handle Problem Language Result Execution time Memory
1039579 2024-07-31T04:48:33 Z 박찬솔(#11028) Toy (CEOI24_toy) C++17
0 / 100
 4 ms 1484 KB 
#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<pld> vpld;
typedef unordered_map<int, int> mpii;

vi UF;

int find(int a) {
    return UF[a] = UF[a] == a ? a : find(UF[a]);
}

void merge(int a, int b) {
    a = find(a), b = find(b);
    UF[a] = b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int w, h, k, l; cin >> w >> h >> k >> l;
    int a, b, c, d; cin >> b >> a >> d >> c;
    int gx, gy;
    vector<vector<int>> vec(h, vi(w));
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++) {
            char c; cin >> c;
            if (c == 'X') vec[i][j] = 1;
            if (c == '*') gx = i, gy = j;
        }
    UF.resize(h * w);
    {
        iota(all(UF), 0);
        vector<vi> sum(h, vi(w));
        for (int i = 0; i < h; i++) {
            int s = 0;
            for (int j = 0; j < w; j++) {
                sum[i][j] = s += vec[i][j];
            }
        }

        auto ok = [&](int i, int j) {
            return sum[i][j + k - 1] - (j ? sum[i][j - 1] : 0) == 0;
        };

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w - k + 1; j++) {
                if (!ok(i, j)) continue;
                if (i && ok(i - 1, j)) merge(i * w + j, (i - 1) * w + j);//, cout << i << " " << j << " " << i - 1 << " " << j << "\n";
                if (j && ok(i, j - 1)) merge(i * w + j, i * w + j - 1);//, cout << i << " " << j << " " << i << " " << j - 1 << "\n";
            }
        }

        int f = 0;
        for (int i = max(0, gy - k + 1); i <= min(w - 1, gy + k - 1); i++) {
            if (find(a * w + b) == find(gx * w + i)) f = 1;
        }

        if (!f) return cout << "NO", 0;
    }
    {
        iota(all(UF), 0);
        vector<vi> sum(h, vi(w));
        for (int j = 0; j < w; j++) {
            int s = 0;
            for (int i = 0; i < h; i++) {
                sum[i][j] = s += vec[i][j];
            }
        }

        auto ok = [&](int i, int j) {
            return sum[i + l - 1][j] - (i ? sum[i - 1][j] : 0) == 0;
        };

        for (int i = 0; i < h - l + 1; i++) {
            for (int j = 0; j < w; j++) {
                if (!ok(i, j)) continue;
                if (i && ok(i - 1, j)) merge(i * w + j, (i - 1) * w + j);//, cout << i << " " << j << " " << i - 1 << " " << j << "\n";
                if (j && ok(i, j - 1)) merge(i * w + j, i * w + j - 1);//, cout << i << " " << j << " " << i << " " << j - 1 << "\n";
            }
        }

        int f = 0;
        for (int i = max(0, gx - l + 1); i <= min(h - 1, gx + l - 1); i++) {
            if (find(c * w + d) == find(i * w + gy)) f = 1;
        }

        if (!f) return cout << "NO", 0;
    }
    cout << "YES";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:71:61: warning: 'gy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |         for (int i = max(0, gy - k + 1); i <= min(w - 1, gy + k - 1); i++) {
      |                                                          ~~~^~~
Main.cpp:72:44: warning: 'gx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   72 |             if (find(a * w + b) == find(gx * w + i)) f = 1;
      |                                         ~~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 4 ms 1392 KB Output is correct
5 Correct 4 ms 1392 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1392 KB Output is correct
8 Correct 4 ms 1392 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 3 ms 1392 KB Output is correct
11 Correct 2 ms 1372 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 2 ms 1372 KB Output is correct
14 Correct 2 ms 1372 KB Output is correct
15 Incorrect 4 ms 1484 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Incorrect 0 ms 348 KB Output isn't correct
16 Halted 0 ms 0 KB -