Submission #878227

#	Time	Username	Problem	Language	Result	Execution time	Memory
878227		406	Reconstruction Project (JOI22_reconstruction)	C++17	35 / 100	5072 ms	22664 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, 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> undo, bk, Es;
vector<ar4> cfr, cbk, fr;
long long td, Wans, cnt = 0;

bool cmp(const ar4 &X, const ar4 &Y) {
        return X[0] < Y[0];
}

inline namespace dsu {
        int 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;
        }
}

inline namespace tree {
        int W[N], node[N], ptr, mn, anc[N], adj[N][2], last;
        vector<ar> Q[N];
        bitset<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;
                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)]) / 2);
        }
        int get() {
                dsu::init();
                mn = INF;
                seen = 0;
                dfs(ptr);
                FOR(i, 0, n) Q[i].clear();
                return mn + 1;
        }
}
ar4 validate(vector<ar4> &E) {
        dsu::init();
        ar4 del = {-1, -1, -1};
        FOR(i, 0, E.size()) {
                auto &[w, u, v] = E[i];
                if (!dsu::merge(u, v)) {
                        del = E[i];
                        E.erase(E.begin() + i);
                        return del;
                }
        }
        return del;
}

void validatefr(vector<ar4> &E) {
        vector<ar4> ok;
        dsu::init();
        for (int i = (int) E.size() - 1; i >= 0; --i) {
                auto &[w, u, v] = E[i];
                if (!dsu::merge(u, v)) {
                        E.erase(E.begin() + i);
                        return;
                }
        }
}

void sol(auto A, bool t) {
        auto &[w, u, v] = A;
        if (dsu::merge(u, v)) {
                Wans += (t ? w : -w);
                td += (t ? -1 : +1);
                (t ? cbk : cfr).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));
        }
}

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] = E[i];
                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;
        //ar3 dar vaghe ar4-e 
        FOR(i, 0, q) {
                int x; cin >> x;
                bool t = false;
                while (p < m && x >= E[p][0]) {
                        fr.insert(lower_bound(fr.begin(), fr.end(), E[p], cmp), E[p]);
                        auto U = undo.back();
                        undo.pop_back();
                        bk.erase(find(bk.begin(), bk.end(), E[p]));
                        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 <= 2 * m + 50);
                        validatefr(fr);
                        dsu::init();
                        Wans = td = 0;
                        minl = INF;
                        cfr.clear(), cbk.clear();
                        int p1 = (int) fr.size() - 1, p2 = 0;
                        while (p1 >= 0 && p2 != bk.size()) {
                                if (x - fr[p1][0] < bk[p2][0] - x)
                                        sol(fr[p1--], 0);
                                else 
                                        sol(bk[p2++], 1);
                        }
                        for (; p1 >= 0; p1--) sol(fr[p1], 0);
                        for (; p2 != bk.size(); p2++) sol(bk[p2], 1);
                        tree::init();
                        for (int i = (int) cbk.size() - 1; i >= 0; --i) {
                                auto &[w, u, v] = cbk[i];
                                tree::merge(u, v, w);
                        }
                        for (auto &A: cfr) {
                                auto &[w, u, v] = A;
                                tree::merge(u, v, w);
                        }
                        minl = tree::get();
                }
                cout << 1ll * td * x + Wans << '\n';
        }
        return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'ar4 validate(std::vector<std::array<int, 3> >&)':
reconstruction.cpp:4:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    4 | #define FOR(i, a, b) for (int i = (a); i < (b); ++i)
      |                                          ^
reconstruction.cpp:88:9: note: in expansion of macro 'FOR'
   88 |         FOR(i, 0, E.size()) {
      |         ^~~
reconstruction.cpp: At global scope:
reconstruction.cpp:111:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  111 | void sol(auto A, bool t) {
      |          ^~~~
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:139:23: warning: unused structured binding declaration [-Wunused-variable]
  139 |                 auto &[w, u, v] = E[i];
      |                       ^~~~~~~~~
reconstruction.cpp:167:46: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |                         while (p1 >= 0 && p2 != bk.size()) {
      |                                           ~~~^~~~~~~~~~~~
reconstruction.cpp:174:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |                         for (; p2 != bk.size(); p2++) sol(bk[p2], 1);
      |                                ~~~^~~~~~~~~~~~

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