Submission #886362

#	Time	Username	Problem	Language	Result	Execution time	Memory
886362		dong_liu	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5059 ms	414872 KiB

reconstruction

#pragma GCC optimize("03,unroll-loops")

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

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using pii = pair<int, int>;

bool mem_st;

const int N = 500, M = 1e5, Q = 1e6;

struct edge {
    int i, j, w;
    bool operator<(const edge e) const {
        return w < e.w;
    }
};

struct arr : ar<int, N-1> {
    int sz = 0;
    void pb(int x) { at(sz++) = x; }
    auto end() { return begin()+sz; }
};

int n, m, q;
edge e[M];
arr pf[M+1], sf[M+1];

struct {
    int p[N];
    void init() {
        for (int i = 0; i < n; i++) p[i] = i;
    }
    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;
    }
} dsu;

bool mem_en;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int h = 0; h < m; h++) {
        cin >> e[h].i >> e[h].j >> e[h].w;
        e[h].i--, e[h].j--;
    }
    sort(e, e+m);
    for (int t = 1; t <= m; t++) {
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                pf[t].pb(h);
        };
        dsu.init();
        ins(t-1);
        for (int h : pf[t-1]) ins(h);
    }
    for (int t = m-1; t >= 0; t--) {
        auto ins = [&](int h) {
            if (dsu.join(e[h].i, e[h].j))
                sf[t].pb(h);
        };
        dsu.init();
        ins(t);
        for (int h : sf[t+1]) ins(h);
    }
    cin >> q;
    int t = 0;
    while (q--) {
        int x;
        cin >> x;
        while (t < m && e[t].w <= x) t++;
        dsu.init();
        int one = 0, two = 0; i64 cost = 0;
        #define ins(h) if (dsu.join(e[h].i, e[h].j)) cost += abs(e[h].w - x)
        while (one < pf[t].sz && two < sf[t].sz)
            if (x-e[pf[t][one]].w < e[sf[t][two]].w-x) {ins(pf[t][one]); one++;}
            else {ins(sf[t][two]); two++;}
        while (one < pf[t].sz) {ins(pf[t][one]); one++;}
        while (two < sf[t].sz) {ins(sf[t][two]); two++;}
        cout << cost << '\n';
    }
#if 0
    cout << double(&mem_en - &mem_st) / (1 << 20) << '\n';
#endif
}

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