Submission #943362

#	Time	Username	Problem	Language	Result	Execution time	Memory
943362		Pannda	Reconstruction Project (JOI22_reconstruction)	C++17	100 / 100	1135 ms	29412 KiB

reconstruction

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> f;
    DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }

    int leader(int u) {
        while (u != f[u]) {
            u = f[u] = f[f[u]];
        }
        return u;
    }

    bool unionize(int u, int v) {
        u = leader(u);
        v = leader(v);
        if (u == v) return false;
        f[v] = u;
        return true;
    }

    bool same(int u, int v) {
        return leader(u) == leader(v);
    }
};

struct Tree {
    const int INF = 1e9 + 12345;
    int n;
    vector<vector<array<int, 2>>> adj;
    Tree(int n) : n(n), adj(n) {}

    void addEdge(int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    void cutEdge(int u, int v, int w) {
        adj[u].erase(find(adj[u].begin(), adj[u].end(), array<int, 2>{v, w}));
        adj[v].erase(find(adj[v].begin(), adj[v].end(), array<int, 2>{u, w}));
    }

    array<int, 3> findMinEdge(int s, int t) {
        vector<array<int, 2>> par(n, array<int, 2>{-1, -1});
        queue<int> que;
        que.push(s);
        par[s] = {s, -1};
        while (!que.empty()) {
            int u = que.front();
            que.pop();
            if (u == t) break;
            for (auto [v, w] : adj[u]) {
                if (par[v][0] == -1) {
                    par[v][0] = u;
                    par[v][1] = w;
                    que.push(v);
                }
            }
        }

        int mn = INF;
        int u, v;
        while (t != s) {
            auto [tt, w] = par[t];
            if (w < mn) {
                mn = w;
                u = t;
                v = tt;
            }
            t = tt;
        }

        return {u, v, mn};
    }
};

int sgn(int x) {
    if (x == 0) return 0;
    return x < 0 ? -1 : +1;
}

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

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

    vector<array<int, 3>> edges(m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        edges[i] = {u, v, w};
    }
    sort(edges.begin(), edges.end(), [&](array<int, 3> e0, array<int, 3> e1) { return e0[2] < e1[2]; });

    vector<array<int, 2>> events_l = [&] {
        vector<array<int, 2>> events;
        DSU dsu(n);
        Tree tree(n);
        for (int i = 0; i < m; i++) {
            auto [u, v, w] = edges[i];
            if (dsu.same(u, v)) {
                auto [uu, vv, ww] = tree.findMinEdge(u, v);
                tree.cutEdge(uu, vv, ww);
                if (ww < w) {
                    events.push_back({(ww + w) / 2 + 1, +w});
                    events.push_back({w + 1, -w});
                }
            } else {
                events.push_back({1, +w});
                events.push_back({w + 1, -w});
            }
            dsu.unionize(u, v);
            tree.addEdge(u, v, w);
        }
        sort(events.begin(), events.end());
        return events;
    }();

    vector<array<int, 2>> events_r = [&] {
        vector<array<int, 2>> events;
        DSU dsu(n);
        Tree tree(n);
        for (int i = m - 1; i >= 0; i--) {
            auto [u, v, w] = edges[i];
            if (dsu.same(u, v)) {
                auto [uu, vv, ww] = tree.findMinEdge(u, v);
                tree.cutEdge(uu, vv, ww);
                ww = -ww;
                events.push_back({w + 1, +w});
                events.push_back({(ww + w) / 2 + 1, -w});
            } else {
                events.push_back({w + 1, +w});
                events.push_back({(int)1e9 + 1, -w});
            }
            dsu.unionize(u, v);
            tree.addEdge(u, v, -w);
        }
        sort(events.begin(), events.end());
        return events;
    }();

    int ptr_l = 0, ptr_r;
    long long sum_l = 0, sum_r = 0;
    long long cnt_l = 0, cnt_r = 0;

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        while (ptr_l < events_l.size() && x >= events_l[ptr_l][0]) {
            sum_l += events_l[ptr_l][1];
            cnt_l += sgn(events_l[ptr_l][1]);
            ptr_l++;
        }
        while (ptr_r < events_r.size() && x >= events_r[ptr_r][0]) {
            sum_r += events_r[ptr_r][1];
            cnt_r += sgn(events_r[ptr_r][1]);
            ptr_r++;
        }
        cout << sum_l - cnt_l * x + cnt_r * x - sum_r << '\n';
    }
}

Compilation message (stderr)

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |         while (ptr_l < events_l.size() && x >= events_l[ptr_l][0]) {
      |                ~~~~~~^~~~~~~~~~~~~~~~~
reconstruction.cpp:161:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |         while (ptr_r < events_r.size() && x >= events_r[ptr_r][0]) {
      |                ~~~~~~^~~~~~~~~~~~~~~~~
reconstruction.cpp: In member function 'std::array<int, 3> Tree::findMinEdge(int, int)':
reconstruction.cpp:74:25: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   74 |         return {u, v, mn};
      |                         ^
reconstruction.cpp:74:25: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
reconstruction.cpp: In function 'int main()':
reconstruction.cpp:161:16: warning: 'ptr_r' may be used uninitialized in this function [-Wmaybe-uninitialized]
  161 |         while (ptr_r < events_r.size() && x >= events_r[ptr_r][0]) {
      |                ^~~~~

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