Submission #874551

#	Time	Username	Problem	Language	Result	Execution time	Memory
874551		406	Reconstruction Project (JOI22_reconstruction)	C++17	3 / 100	5088 ms	7340 KiB

reconstruction

#pragma GCC optimize ("Ofast,unroll-loops")
#pragma GCC target("avx2")
//besmellah
#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)))
using namespace std;
using ar = array<int, 2>;
using ar3 = array<int, 3>;

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;
ar3 W[N], E[M], hame[2 * N];
bitset<N> seen;

void dfs(int v, int p) {
        seen[v] = true;
        for (auto [u, w]: adj[v]) if (u != p) {
                W[u] = max(W[v], {w, u, v});
                dfs(u, v);
        }
}

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);
        vector<ar3> undo;
        deque<ar3> Es;
        for (int i = m - 1; i >= 0; i--) { //ino mishe behtar kard ba DSU vali halesh nist (orderesham ye log kamtar dare)
                auto [w, u, v] = E[i];
                W[u] = {-INF, u, u};
                seen = 0;
                dfs(u, u);

                if (seen[v]) {
                        auto [dw, du, dv] = W[v];
                        if (du > dv) swap(du, dv);
                        ers(du, (ar{dv, dw}));
                        ers(dv, (ar{du, dw}));
                        Es.erase(find(Es.begin(), Es.end(), ar3{dw, du, dv}));
                        //cout << "DELETING " << du + 1 << ' ' << dv + 1 << " " << dw << endl;
                        undo.push_back({dw, du, dv});
                }
                else 
                        undo.push_back({-1, -1, -1});
                //cout << "ADDING " << u + 1 << ' ' << v + 1 << ' ' << w << endl;
                Es.push_back(E[i]);
                adj[v].push_back({u, w});
                adj[u].push_back({v, w});
        }
        //for (auto [w, u, v]: Es) cout << u << ' ' << v << ' ' << w << endl;
        //now MST at zero
        vector<ar3> jelo;
        
        //be zaman ahamiat nemidaham
        int q; cin >> q; int p = 0;
        while (q--) {
                int x; cin >> x;
                bool t = false;
                while (p < m && E[p][0] < x) { //ino hesesh bood vali log ziad dare
                        jelo.push_back(E[p]);
                        t = true;

                        Es.erase(find(Es.begin(), Es.end(), E[p]));
                        auto akh = undo.back();
                        undo.pop_back();
                        if (akh[0] != -1) Es.push_back(akh);
                        ++p;
                        sort(Es.begin(), Es.end());
                        assert(Es.size() < N);
                }
                if (t) {
                        vector<ar3> ok;
                        ok.reserve(jelo.size());
                        dsu::init();
                        sort(jelo.rbegin(), jelo.rend());
                        for (auto [w, u, v]: jelo) if (dsu::merge(u, v)) ok.push_back({w, u, v});
                        jelo = ok;
                        assert(jelo.size() < N);
                }

                //jelo -> small to large (x - w)
                //Es -> small to large (x - w)
                int p1 = 0, p2 = 0;
                dsu::init();
                long long ans = 0;
                int cnt = 0;
                while (p1 != jelo.size() || p2 != Es.size()) {
                        int w, u, v;
                        if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x))) {
                                w = x - jelo[p1][0], u = jelo[p1][1], v = jelo[p1][2]; ++p1;
                        }
                        else {
                                w = Es[p2][0] - x, u = Es[p2][1], v = Es[p2][2]; ++p2;
                        }
                        bool t = dsu::merge(u, v);
                        ans += t ? w : 0;
                        cnt += t;
                        if (cnt == n - 1) break;
                }
                cout << ans << '\n';
        }

        return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:115:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 while (p1 != jelo.size() || p2 != Es.size()) {
      |                        ~~~^~~~~~~~~~~~~~
reconstruction.cpp:115:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |                 while (p1 != jelo.size() || p2 != Es.size()) {
      |                                             ~~~^~~~~~~~~~~~
reconstruction.cpp:117:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                         if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x))) {
      |                             ~~~^~~~~~~~~~~~
reconstruction.cpp:117:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |                         if (p2 == Es.size() || (p1 != jelo.size() && (x - jelo[p1][0]) < (Es[p2][0] - x))) {
      |                                                 ~~~^~~~~~~~~~~~~~

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