Submission #705849

#	Time	Username	Problem	Language	Result	Execution time	Memory
705849		piOOE	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	932 ms	33184 KiB

reconstruction

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct Line {
    ll k = 0, b = 0;

    Line(ll k = 0, ll b = 0) : k(k), b(b) {}

    ll eval(ll x) {
        return k * x + b;
    }

    friend Line operator+(const Line &a, const Line &c) {
        return {a.k + c.k, a.b + c.b};
    }
};

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

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;
}

bool same(int x, int y) {
    return leader(x) == leader(y);
}

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);

    vector<array<int, 3>> mst;
    vector<pair<int, Line>> events;

    for (int i = m - 1; i >= 0; --i) {
        init();

        auto [wi, x, y] = e[i];
        events.emplace_back(wi, Line(2, -2 * wi));

        mst.insert(mst.begin(), e[i]);

        for (int j = 1; j < mst.size(); ++j) {
            auto [w, a, b] = mst[j];

            unite(a, b);

            if (same(x, y)) {
                int mid = (wi + w + 1) / 2;

                events.emplace_back(mid, Line(-1, wi));
                events.emplace_back(mid, Line(-1, w));

                mst.erase(mst.begin() + j);

                break;
            }
        }
    }

    init();

    for (int i = 0; i < m; ++i) {
        auto [w, a, b] = e[i];

        if (unite(a, b)) {
            events.emplace_back(-1, Line(-1, w));
        }
    }

    sort(events.begin(), events.end(), [&](auto &x, auto &y) {
        return x.first < y.first;
    });

    Line res{};

    int q;
    cin >> q;

    int i = 0;

    while (q--) {
        int x;
        cin >> x;

        while (i < events.size() && events[i].first <= x) {
            res = res + events[i++].second;
        }

        cout << res.eval(x) << '\n';
    }

    return 0;
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:81: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]
   81 |         for (int j = 1; j < mst.size(); ++j) {
      |                         ~~^~~~~~~~~~~~
reconstruction.cpp:124:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, Line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         while (i < events.size() && events[i].first <= x) {
      |                ~~^~~~~~~~~~~~~~~

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