Submission #812724

#	Time	Username	Problem	Language	Result	Execution time	Memory
812724		piOOE	Garden (JOI23_garden)	C++17	100 / 100	469 ms	8272 KiB

garden

#include <bits/stdc++.h>

using namespace std;

struct Cycle {
    vector<bool> a;
    vector<int> nxt, prv;
    int n = 0, mx = 0, cnt = 0;

    Cycle(int n) : n(n), mx(0), cnt(0), a(n, 0), nxt(n), prv(n) {}

    void ins(int i) {
        a[i] = true;
        int l = i == 0 ? n - 1 : i - 1, r = i + 1 == n ? 0 : i + 1;
        prv[i] = a[l] ? prv[l] : i, nxt[i] = a[r] ? nxt[r] : i;
        nxt[prv[i]] = nxt[i], prv[nxt[i]] = prv[i];
        mx = max(mx, (nxt[i] - prv[i] + n) % n + 1);
    }
};

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

    int n, m, d;
    cin >> n >> m >> d;

    vector<int> needx(2 * d), needy(2 * d);
    vector<vector<int>> points(2 * d);

    for (int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        needx[a] = needy[b] = true;
    }

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        if (needx[a] || needy[b]) {
            continue;
        }
        points[a].push_back(b);
    }

    for (int i = 0; i < d; ++i) {
        needx[i + d] = needx[i];
        needy[i + d] = needy[i];
        points[i + d] = points[i];
    }

    int ans = d * d;
    vector<vector<int>> lastVec(2 * d);

    for (int L = 1; L <= d; ++L) {
        if (!needx[L - 1]) {
            continue;
        }
        int R = L;
        while (!needx[R]) {
            R += 1;
        }
        vector<int> last(d, -1);
        for (int l = R - 1; l >= L; --l) {
            for (int y : points[l]) {
                last[y] = l;
            }
            for (int i = l; i < R; ++i) {
                lastVec[i].clear();
            }
            Cycle c(d);
            for (int y = 0; y < d; ++y) {
                if (needy[y]) {
                    continue;
                }
                if (last[y] == -1) {
                    c.ins(y);
                } else {
                    lastVec[last[y]].push_back(y);
                }
            }
            for (int r = R; r >= l; --r) {
                if (r < R) {
                    for (int y : lastVec[r]) {
                        c.ins(y);
                    }
                }
                ans = min(ans, (d - (r - l)) * (d - c.mx));
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

garden.cpp: In constructor 'Cycle::Cycle(int)':
garden.cpp:8:24: warning: 'Cycle::cnt' will be initialized after [-Wreorder]
    8 |     int n = 0, mx = 0, cnt = 0;
      |                        ^~~
garden.cpp:6:18: warning:   'std::vector<bool> Cycle::a' [-Wreorder]
    6 |     vector<bool> a;
      |                  ^
garden.cpp:10:5: warning:   when initialized here [-Wreorder]
   10 |     Cycle(int n) : n(n), mx(0), cnt(0), a(n, 0), nxt(n), prv(n) {}
      |     ^~~~~

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25