Submission #876953

#	Time	Username	Problem	Language	Result	Execution time	Memory
876953		406	Reconstruction Project (JOI22_reconstruction)	C++17	0 / 100	1 ms	604 KiB

reconstruction

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
//besmellah
//accept sho :D
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ers(v, X) adj[v].erase(find(adj[v].begin(), adj[v].end(), (X)))
#define int long long
using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 4>;
using ar5 = array<int, 5>;

const int M = 1e5 + 5, N = 505, Q = 1e6 + 5;
const long long INF = 1ll << 30;

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;
        }
}
vector<ar> adj[N];
int n, m, W[N], L[M];
ar3 E[M];
bitset<N> seen;
vector<ar3> Es, undo, bk;

void dfsmn(int v, int p) {
        seen[v] = true;
        for (auto [u, w]: adj[v]) if (u != p) {
                W[u] = min(W[v], w);
                dfsmn(u, v);
        }
}
void build() {
        FOR(i, 0, n) adj[i].clear();
        seen = 0;
        for (auto [w, u, v, l]: Es) {
                adj[u].push_back({v, w});
                adj[v].push_back({u, w});
        }
}
ar3 validate(vector<ar3> &E) {
        sort(E.begin(), E.end());
        vector<ar3> ok;
        dsu::init();
        ar3 del = {-1, -1, -1, -1};
        for (auto [w, u, v, l]: E) {
                if (dsu::merge(u, v))
                        ok.push_back({w, u, v, l});
                else del = {w, u, v, l};
        }
        E = 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(i, 0, m) {
                auto [w, u, v, l] = E[i];
                build();
                W[u] = INF;
                dfsmn(u, u);
                if (seen[v])
                        E[i][3] = (W[v] + w + 1) / 2;
                else 
                        E[i][3] = -INF;
                Es.push_back(E[i]);
                validate(Es);
        }
        for (int i = m - 1; i >= 0; --i) {
                auto [w, u, v, l] = E[i];
                bk.push_back(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<ar3> fr;
        FOR(i, 0, q) {
                int x; cin >> x;
                bool t = false;
                while (p < m && x >= E[p][0]) {
                        fr.push_back(E[p]);
                        fr.back()[0] *= -1;
                        auto U = undo.back();
                        undo.pop_back();
                        bk.erase(find(bk.begin(), bk.end(), E[p]));
                        if (U[0] != -1) bk.push_back(U);
                        //cout << "BK .push() " << U[0] << endl;
                        ++p;
                        t = true;
                }
                if (t || x >= minl) { //build_mst() (M bar hadeaksar)
                        assert(++cnt <= 2 * m);
                        validate(fr);
                        dsu::init();
                        W = td = 0;
                        minl = INF;
                        //al = bk + fr (bt)
                        vector<ar5> al; //badihish
                        //cout <<"QUERY" << endl;
                        for (auto [w, u, v, l]: fr) { //w = -w
                                assert(w <= x);
                                al.push_back({x + w, u, v, l, 0});
                                //cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
                        }
                        //cout << "---" << endl;
                        for (auto [w, u, v, l]: bk) {
                                assert(w >= x);
                                al.push_back({w - x, u, v, l, 1});
                                //cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
                        }
                        //
                        //cout << "---" << endl;
                        //int ans = 0;
                        sort(al.begin(), al.end(), [&](const auto &X, const auto &Y) {return X[0] < Y[0];});
                        for (auto [w, v, u, l, t]: al) {
                                w = (t ? w + x : x - w);
                                //cout << u + 1 << ' ' << v + 1 << ' ' << w << endl;
                                if (dsu::merge(u, v)) {
                                        //ans += abs(w - x);
                                        W += (t ? w : -w);
                                        td += (t ? -1 : +1);
                                }
                                else if (t) {
                                       minl = min(minl, l); 
                                }
                                else {
                                        fr.erase(find(fr.begin(), fr.end(), ar3{-w, u, v, l}));
                                }
                        }
                        //cout << ans << endl;
                }
                cout << 1ll * td * x + W << '\n';
        }
        return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:93:22: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   93 |                 auto [w, u, v, l] = E[i];
      |                      ^~~~~~~~~~~~
reconstruction.cpp:157:40: warning: 'W' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |                 cout << 1ll * td * x + W << '\n';
      |                                        ^
reconstruction.cpp:157:34: warning: 'td' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |                 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