제출 #830916

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830916		vjudge1	Garden (JOI23_garden)	C++17	75 / 100	3073 ms	7228 KiB

garden

#include <bits/stdc++.h>

using namespace std;

struct dsu
{
    int n;
    vector<int> parent;
    vector<int> sz;
    int ans = 0;
    void resize(int _n)
    {
        n = _n;
        parent = vector<int>(n, -1);
        sz = vector<int>(n);
    }
    void make_set(int qui)
    {
        if (parent[qui] != -1)
        {
            return;
        }
        parent[qui] = qui;
        sz[qui] = 1;
        ans = max(ans, 1);
    }
    pair<int, int> find_set(int u)
    {
        if (parent[u] == -1)
        {
            return {-1, 0};
        }
        if (parent[u] == u)
        {
            return {u, sz[u]};
        }
        pair<int, int> ans = find_set(parent[u]);
        parent[u] = ans.first;
        return ans;
    }
    void unite(int u, int v)
    {
        if (parent[u] == -1 || parent[v] == -1)
        {
            return;
        }
        u = find_set(u).first;
        v = find_set(v).first;
        if (u == v)
        {
            return;
        }

        if (sz[u] > sz[v])
        {
            swap(u, v);
        }
        parent[u] = v;
        sz[v] += sz[u];
        ans = max(ans, sz[v]);
    }
    int getmax()
    {
        return max(ans, find_set(0).second + find_set(n - 1).second);
    }
};

int32_t main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int d, n, m;
    cin >> n >> m >> d;
    vector<pair<int, int>> si(n + 1);
    vector<pair<int, int>> sau(m + 1);

    vector<bool> isneeded(d);

    for (int i = 1; i <= n; ++i)
    {
        cin >> si[i].first >> si[i].second;
        isneeded[si[i].first] = true;
    }
    vector<vector<int>> adam(d);
    for (int i = 1; i <= m; ++i)
    {
        cin >> sau[i].first >> sau[i].second;
        adam[sau[i].first].push_back(sau[i].second);
    }

    vector<int> must(d + 1);
    vector<int> cnt_copy(d + 1);

    for (int j = 1; j <= n; ++j)
    {
        must[si[j].second] = 1;
    }
    for (int j = 1; j <= m; ++j)
    {
        cnt_copy[sau[j].second]++;
    }

    int ans = INT_MAX;
    for (int i = 0; i < d; ++i)
    {
        dsu tree;
        tree.resize(d);
        int pos = 0;
        vector<int> cnt = cnt_copy;

        for (int j = 0; j < d; ++j)
        {
            if (!cnt[j] && !must[j])
            {
                tree.make_set(j);
            }
        }
        for (int j = 0; j < d; ++j)
        {
            if (!cnt[j] && !must[j])
            {
                if (j != 0)
                {
                    tree.unite(j - 1, j);
                }
                if (j != d - 1)
                {
                    tree.unite(j, j + 1);
                }
            }
        }
        for (int j = i; j < i + d; ++j)
        {
            if (isneeded[j % d])
            {
                pos = j;
            }
        }
        for (int j = i; j < pos; ++j)
        {
            if (adam[j % d].empty())
                continue;
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    cnt[k]--;
                    if (cnt[k] == 0)
                    {
                        tree.make_set(k);
                    }
                }
            }
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    if (cnt[k] == 0)
                    {
                        if (k != 0)
                        {
                            tree.unite(k - 1, k);
                        }
                        if (k != d - 1)
                        {
                            tree.unite(k, k + 1);
                        }
                    }
                }
            }
        }
        for (int j = pos; j < i + d; ++j)
        {
            if (adam[j % d].empty() && j != pos)
                continue;
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    cnt[k]--;
                    if (cnt[k] == 0)
                    {
                        tree.make_set(k);
                    }
                }
            }
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    if (cnt[k] == 0)
                    {
                        if (k != 0)
                        {
                            tree.unite(k - 1, k);
                        }
                        if (k != d - 1)
                        {
                            tree.unite(k, k + 1);
                        }
                    }
                }
            }
            // cout << i << ' ' << j << ' ' << d - tree.getmax() << '\n';
            if (ans > (j - i + 1) * (d - tree.getmax()))
            {
                ans = (j - i + 1) * (d - tree.getmax());
            }
        }
    }
    cout << ans;
}

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