Submission #884726

#	Time	Username	Problem	Language	Result	Execution time	Memory
884726		406	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	456 ms	21172 KiB

reconstruction

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar4 = array<int, 4>;
using ar3 = array<int, 3>;
const int M = 1e5 + 5, N = 1002, Q = 1e6 + 5;
const long long INF = 1e9 + 2;
int n, m;
ar4 E[M];
vector<ar4> bk;
inline namespace dsu {
        short dpr[N];
        void init() {
                memset(dpr, -1, sizeof dpr);
        }
        int gpr(int x) {
                return dpr[x] < 0 ? x : dpr[x] = gpr(dpr[x]);
        }
        bool merge(int u, int v) {
                u = gpr(u), v = gpr(v);
                if (u == v) return false;
                if (dpr[u] < dpr[v]) swap(u, v);
                dpr[v] += dpr[u];
                dpr[u] = v;
                return true;
        }
}

int validate(vector<ar4> &E) {
        dsu::init();
        for (int i = (int) E.size() - 1; ~i; --i) {
                auto [w, u, v, id] = E[i];
                if (!dsu::merge(u, v)) {
                        E.erase(E.begin() + i);
                        return id;
                }
        }
        return -1;
}
int R[M], L[M];

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        vector<ar3> V;
        FOR(i, 0, m) {
                cin >> E[i][1] >> E[i][2] >> E[i][0];
                --E[i][1], --E[i][2];
                if (E[i][1] > E[i][2]) swap(E[i][1], E[i][2]);
                V.push_back({E[i][0], E[i][0] * -2, 2});
        }
        sort(E, E + m);
        FOR(i, 0, m) E[i][3] = i;
        FOR(i, 0, m) {
                auto &[w, u, v, id1] = E[i];
                bk.insert(lower_bound(bk.begin(), bk.end(), E[i]), E[i]);
                int id = validate(bk);
                if (id == -1) L[i] = -INF;
                else {
                        L[i] = (w + E[id][0] + 1) / 2;
                        R[id] = (w + E[id][0] + 1) / 2;
                        V.push_back({R[id], E[id][0], -1});
                }
                V.push_back({L[i], E[i][0], -1});
        }
        sort(V.rbegin(), V.rend());
        long long q, S = 0, td = 0; cin >> q;
        FOR(i, 0, q) {
                int x; cin >> x;
                while (V.size() && V.back()[0] <= x) {
                        auto a = V.back();
                        V.pop_back();
                        S += a[1];
                        td += a[2];
                }
                cout << S + x * td << '\n';
        }
        return 0;
}

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