Submission #704676

#	Time	Username	Problem	Language	Result	Execution time	Memory
704676		piOOE	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5096 ms	600800 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int Q = 1e5 + 1, N = 500;

vector<array<int, 3>> save[Q];
array<int, 3> e[Q];

int fa[N];

void init() {
    iota(fa, fa + N, 0);
}

int leader(int x) {
    while (x != fa[x]) x = fa[x] = fa[fa[x]];
    return x;
}

bool unite(int x, int y) {
    x = leader(x), y = leader(y);

    if (x == y) {
        return false;
    }

    fa[y] = x;

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; ++i) {
        cin >> e[i][1] >> e[i][2] >> e[i][0];
        e[i][1] -= 1, e[i][2] -= 1;
    }

    sort(e, e + m);

    int q;
    cin >> q;

    vector<int> X(q);
    vector<ll> ans(q);

    for (int &x : X) {
        cin >> x;
    }

    constexpr int inf = 2e9;

    for (int t = 0; t < 2; ++t) {
        vector<array<int, 3>> mst;

        int pnt = 0;

        for (int i = 0; i <= m; ++i) {
            if (i > 0) {
                mst.insert(mst.begin(), e[(t == 0 ? m - i : i - 1)]);
                init();

                for (int ii = 0; ii < mst.size(); ++ii) {
                    if (!unite(mst[ii][1], mst[ii][2])) {
                        mst.erase(mst.begin() + ii);
                        break;
                    }
                }

                if (t == 0) {
                    save[m - i] = mst;
                }
            }

            if (t == 1) {
                auto oth = save[i];

                while (pnt < q && X[pnt] < (i == m ? inf : e[i][0])) {
                    init();

                    int L = 0, R = 0, cnt = 0;

                    while (cnt < n - 1) {
                        int weightL = L == mst.size() ? inf : X[pnt] - mst[L][0];
                        int weightR = R == oth.size() ? inf : oth[R][0] - X[pnt];

                        if (weightL < weightR) {
                            if (unite(mst[L][1], mst[L][2])) {
                                ans[pnt] += weightL;
                                cnt += 1;
                            }

                            L += 1;
                        } else {
                            if (unite(oth[R][1], oth[R][2])) {
                                ans[pnt] += weightR;
                                cnt += 1;
                            }

                            R += 1;
                        }
                    }

                    pnt += 1;
                }
            }
        }
    }

    for (int i = 0; i < q; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:70:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |                 for (int ii = 0; ii < mst.size(); ++ii) {
      |                                  ~~~^~~~~~~~~~~~
reconstruction.cpp:91:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |                         int weightL = L == mst.size() ? inf : X[pnt] - mst[L][0];
      |                                       ~~^~~~~~~~~~~~~
reconstruction.cpp:92:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |                         int weightR = R == oth.size() ? inf : oth[R][0] - X[pnt];
      |                                       ~~^~~~~~~~~~~~~

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