Submission #886916

#	Time	Username	Problem	Language	Result	Execution time	Memory
886916		box	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1322 ms	28704 KiB

reconstruction

/*
The problem is equivalent to finding the MST with weights abs(w_i - x).
If we sort the edges, the MST will be N - 1 edges in a range.
When we shift a range rightwards, we replace the leftmost edge with the new rightmost edge.
Therefore, in some sense, for each edge we can find the edge to the left that it replaces.
We can do this by looking at the MST created by the previous edges and find the first point where u_i and v_i are connected.
Now, using the fact that the function is abs(w_i - x) we can find the intersection of the two functions, allowing us to build a piecewise function and answer the queries.
*/
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 500;

int p[N];

void init(int n) {
    iota(p, p + n, 0);
}
int find(int i) {
    return p[i] == i ? i : p[i] = find(p[i]);
}
bool join(int i, int j) {
    i = find(i), j = find(j);
    if (i == j) return false;
    p[i] = j;
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<ar<int, 3>> ed(m);
    for (auto &[w, i, j] : ed) cin >> i >> j >> w, i--, j--;
    sort(begin(ed), end(ed));
    vector<int> opt;
    vector<ar<int, 3>> dy;
    for (int h = 0; h < m; h++) {
        auto [w, i, j] = ed[h];
        init(n);
        int p = -1;
        for (int h_ : opt) {
            join(ed[h_][1], ed[h_][2]);
            if (find(i) == find(j)) {
                p = h_;
                break;
            }
        }
        dy.push_back({w, 2, -2 * w});
        dy.push_back({p == -1 ? -1 : (w + ed[p][0] + 1) / 2, p == -1 ? -1 : -2, p == -1 ? w : w + ed[p][0]});
        init(n);
        opt.insert(begin(opt), h);
        int s = 0;
        for (int t = 0; t < sz(opt); t++) if (join(ed[opt[t]][1], ed[opt[t]][2]))
            opt[s++] = opt[t];
        opt.resize(s);
    }
    sort(begin(dy), end(dy));
    int q;
    cin >> q;
    i64 x0 = 0, x1 = 0;
    int p = 0;
    while (q--) {
        int x;
        cin >> x;
        while (p < sz(dy) && dy[p][0] <= x) {
            x1 += dy[p][1];
            x0 += dy[p][2];
            p++;
        }
        cout << x * x1 + x0 << '\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