Submission #704668

#	Time	Username	Problem	Language	Result	Execution time	Memory
704668		piOOE	Reconstruction Project (JOI22_reconstruction)	C++17	42 / 100	5061 ms	223252 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

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

int fa[N], sz[N];

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

int leader(int x) {
    return x == fa[x] ? x : fa[x] = leader(fa[x]);
}

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

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

    if (sz[x] < sz[y]) {
        swap(x, y);
    }

    fa[y] = x;
    sz[x] += sz[y];

    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<int> mst;

        int pnt = 0;

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

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

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

            if (t == 1) {
                vector<int> 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] - e[mst[L]][0];
                        int weightR = R == oth.size() ? inf : e[oth[R]][0] - X[pnt];

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

                            L += 1;
                        } else {
                            if (unite(e[oth[R]][1], e[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:75:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for (int ii = 0; ii < mst.size(); ++ii) {
      |                                  ~~~^~~~~~~~~~~~
reconstruction.cpp:96:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |                         int weightL = L == mst.size() ? inf : X[pnt] - e[mst[L]][0];
      |                                       ~~^~~~~~~~~~~~~
reconstruction.cpp:97:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |                         int weightR = R == oth.size() ? inf : e[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