Submission #830868

#	Time	Username	Problem	Language	Result	Execution time	Memory
830868		vjudge1	Garden (JOI23_garden)	C++17	0 / 100	3087 ms	4368 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);
    }
    int ans = INT_MAX;
    for (int i = 0; i < d; ++i)
    {
        dsu tree;
        tree.resize(d);
        int pos = 0;
        vector<int> f(d);
        vector<int> must(d);
        for (int j = 1; j <= n; ++j)
        {
            must[si[j].second] = 1;
            f[si[j].second] = 1;
        }
        for (int j = 1; j <= m; ++j)
        {
            f[sau[j].second] = 1;
        }
        for (int j = 0; j < d; ++j)
        {
            if (!f[j])
            {
                tree.make_set(j);
            }
        }
        for (int j = 0; j < d; ++j)
        {
            if (!f[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)
        {
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    tree.make_set(k);
                }
            }
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    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)
        {
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    tree.make_set(k);
                }
            }
            for (auto k : adam[j % d])
            {
                if (!must[k])
                {
                    if (k != 0)
                    {
                        tree.unite(k - 1, k);
                    }
                    if (k != d - 1)
                    {
                        tree.unite(k, k + 1);
                    }
                }
            }
            assert(tree.getmax() < d);
            ans = min(ans, (j - i + 1) * (d - tree.getmax()));
        }
    }
    cout << ans;
}

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