Submission #878146

#	Time	Username	Problem	Language	Result	Execution time	Memory
878146		406	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	297 ms	7180 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)
//#define int long long
using namespace std;
using ar = array<int, 2>;
using ar4 = array<int, 4>;

const int M = 1e5 + 5, N = 505, Q = 1e6 + 5;
const long long INF = 1e9 + 2;

int n, m;
ar4 E[M];
vector<ar4> undo, bk, Es;

inline namespace dsu {
        int dpr[2 * 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;
        }
}

inline namespace tree {
        int W[2 * N], node[N], ptr, mn, anc[2 * N], adj[2 * N][2], last;
        vector<ar> Q[N];
        bitset<2 * N> seen;
        void init() {
                dsu::init();
                iota(node, node + N, 0);
                memset(adj, -1, sizeof adj);
                ptr = n - 1;
                last = -INF;
        }
        void merge(int u, int v, int w) {
                int tu = node[dsu::gpr(u)], tv = node[dsu::gpr(v)];
                if (tu == tv) return;
                assert(w >= last);
                last = w;
                dsu::merge(u, v); 
                node[gpr(u)] = ++ptr;
                adj[ptr][0] = tu;
                adj[ptr][1] = tv;
                //cout << "PAR OF " << adj[ptr][0] << " AND " << adj[ptr][1] << " IS " << ptr << endl;
                W[ptr] = w;
        }
        void dfs(int v) {
                //cout << "DFS AT V: " << v + 1 << endl;
                seen[v] = true;
                FOR(i, 0, 2) if (adj[v][i] != -1) {
                        int u = adj[v][i];
                        assert(!seen[u]);
                        dfs(u);
                        dsu::merge(u, v);
                        anc[dsu::gpr(v)] = W[v];
                }
                for (auto [u, w]: Q[v]) if (seen[u]) 
                        mn = min(mn, w + anc[gpr(u)]);
        }
        int get() {
                dsu::init();
                mn = INF;
                seen = 0;
                dfs(ptr);
                FOR(i, 0, n) Q[i].clear();
                return (mn - 2) >> 1;
        }
}
inline bool cmp(const ar4 &X, const ar4 &Y) {
        return X[0] < Y[0];
}
        
ar4 validate(vector<ar4> &E) {
        vector<ar4> ok;
        ok.reserve(E.size());
        dsu::init();
        ar4 del = {-1, -1, -1, -1};
        for (auto A: E) {
                auto [w, u, v, t] = A;
                if (dsu::merge(u, v))
                        ok.push_back(A);
                else del = A;
        }
        E.swap(ok);
        return del;
}

signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr); 
        cin >> n >> m;
        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]);
        }
        sort(E, E + m);
        for (int i = m - 1; i >= 0; --i) {
                auto &[w, u, v, t] = E[i];
                t = 1;
                bk.insert(lower_bound(bk.begin(), bk.end(), E[i], cmp), E[i]);
                undo.push_back(validate(bk));
        }
        int q; cin >> q;
        int p = 0, minl = -INF;
        long long td, W, cnt = 0;
        //ar3 dar vaghe ar4-e 
        vector<ar4> fr;
        FOR(i, 0, q) {
                int x; cin >> x;
                bool t = false;
                while (p < m && x >= E[p][0]) {
                        ar4 X = {-E[p][0], E[p][1], E[p][2], 0};
                        fr.insert(lower_bound(fr.begin(), fr.end(), X, cmp), X);
                        auto U = undo.back();
                        undo.pop_back();
                        bk.erase(find_if(bk.begin(), bk.end(), [&](const auto &X) {
                                        return X[0] == E[p][0] && X[1] == E[p][1] && X[2] == E[p][2];
                        }));
                        if (U[0] != -1)
                                bk.insert(lower_bound(bk.begin(), bk.end(), U, cmp), U);
                        ++p;
                        t = true;
                }
                if (t || x >= minl) { //build_mst() (M bar hadeaksar)
                        assert(++cnt <= 5 * m);
                        validate(fr);
                        dsu::init();
                        W = td = 0;
                        minl = INF;
                        //al = bk + fr (bt)
                        vector<ar4> al; //badihish
                        al.resize(fr.size() + bk.size());
                        for (auto &A: fr) A[0] += x;
                        for (auto &A: bk) A[0] -= x;
                        merge(fr.begin(), fr.end(), bk.begin(), bk.end(), al.begin(), cmp);
                        for (auto &A: fr) A[0] -= x;
                        for (auto &A: bk) A[0] += x;
                        //sort(al.begin(), al.end());
                        vector<ar4> cfr, cbk;
                        for (auto A: al) {
                                auto &[w, u, v, t] = A;
                                w = (t ? w + x : x - w);
                                if (dsu::merge(u, v)) {
                                        W += (t ? w : -w);
                                        td += (t ? -1 : +1);
                                        (!t ? cfr : cbk).push_back(A);
                                }
                                else if (t) {
                                        tree::Q[v].push_back({u, w});
                                        tree::Q[u].push_back({v, w});
                                }
                                else {
                                        A[0] *= -1;
                                        fr.erase(find(fr.begin(), fr.end(), A));
                                }
                        }
                        tree::init();
                        reverse(cfr.begin(), cfr.end());
                        for (auto A: cfr) {
                                auto &[w, u, v, t] = A;
                                tree::merge(u, v, w);
                        }
                        for (auto A: cbk) {
                                auto &[w, u, v, t] = A;
                                tree::merge(u, v, w);
                        }
                        minl = tree::get();
                }
                cout << 1ll * td * x + W << '\n';
        }
        return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:181:40: warning: 'W' may be used uninitialized in this function [-Wmaybe-uninitialized]
  181 |                 cout << 1ll * td * x + W << '\n';
      |                                        ^
reconstruction.cpp:181:34: warning: 'td' may be used uninitialized in this function [-Wmaybe-uninitialized]
  181 |                 cout << 1ll * td * x + W << '\n';
      |                         ~~~~~~~~~^~~

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