Submission #1313956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313956		mikolaj00	Reconstruction Project (JOI22_reconstruction)	C++20	100 / 100	1267 ms	23020 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct DSU
{
    DSU(int size) : arr(size), size(size, 1)
    {
        for (int i = 0; i < arr.size(); i++)
            arr[i] = i;
    }

    int find(int k)
    {
        if (arr[k] == k)
            return k;
        return arr[k] = find(arr[k]);
    }

    inline bool connected(int a, int b)
    {
        return find(a) == find(b);
    }

    void join(int a, int b)
    {
        if (connected(a, b))
            return;

        int r_a = find(a), r_b = find(b);
        if (size[r_a] < size[r_b])
            swap(r_a, r_b);

        size[r_a] += size[r_b];
        arr[r_b] = r_a;
    }

    vector<int> size;
    vector<int> arr;
};

struct Edge
{
    int u, v;
    ll w;

    bool operator<(Edge const& other)
    {
        return w < other.w;
    }
};

struct Sweep
{
    ll t, a, b;

    bool operator<(Sweep const& other)
    {
        return t < other.t;
    }
};

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

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

    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    sort(edges.begin(), edges.end());

    vector<int> l(m, -1e9), r(m, 1e9);
    for (int i = 0; i < m; i++)
    {
        DSU dsu(n+1);
        for (int j = i-1; j >= 0; j--)
        {
            dsu.join(edges[j].u, edges[j].v);
            if (dsu.connected(edges[i].u, edges[i].v))
            {
                l[i] = (edges[i].w + edges[j].w)/2 + 1;
                break;
            }
        }
    }

    for (int i = 0; i < m; i++)
    {
        DSU dsu(n+1);
        for (int j = i+1; j < m; j++)
        {
            dsu.join(edges[j].u, edges[j].v);
            if (dsu.connected(edges[i].u, edges[i].v))
            {
                r[i] = (edges[i].w + edges[j].w)/2;
                break;
            }
        }
    }

    vector<Sweep> sweep;
    for (int i = 0; i < m; i++)
    {
        sweep.push_back({l[i], -1LL, edges[i].w});
        sweep.push_back({edges[i].w, 2LL, -2LL*edges[i].w});
        sweep.push_back({r[i]+1, -1LL, edges[i].w});
    }
    sort(sweep.begin(), sweep.end());

    int idx = 0;
    ll a = 0, b = 0;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        int x;
        cin >> x;

        while (idx < sweep.size() && sweep[idx].t <= x)
        {
            a += sweep[idx].a;
            b += sweep[idx].b;
            idx++;
        }

        ll ans = a*x + b;
        cout << ans << '\n';
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 7 / 7
• Subtask 4: 28 / 28
• Subtask 5: 35 / 35
• Subtask 6: 23 / 23