Submission #677923

#	Time	Username	Problem	Language	Result	Execution time	Memory
677923		FedShat	Bridges (APIO19_bridges)	C++17	100 / 100	2660 ms	12160 KiB

bridges

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

#ifdef __APPLE__
#include "../../debug.h"
#else
#define debug(...) 42
#endif

struct DSU {
    vector<int> p, sz;
    vector<array<int, 4>> rb; // v, u, p[v], sz[u]

    DSU(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.resize(n, 1);
    }

    int get(int v) {
        if (p[v] == v) {
            return v;
        }
        return get(p[v]);
    }

    void unite(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        if (sz[u] < sz[v]) {
            swap(u, v);
        }
        rb.push_back({v, u, p[v], sz[u]});
        p[v] = u;
        sz[u] += sz[v];
    }

    // void print() {
    //     for (int i = 0; i < (int) p.size(); ++i) {
    //         cout << p[i] + 1 << " " << i + 1 << "\n";
    //     }
    // }

    void rollback(int x) {
        while ((int) rb.size() > x) {
            auto [v, u, pv, szu] = rb.back();
            rb.pop_back();
            p[v] = pv;
            sz[u] = szu;
        }
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> ed(m);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        --u;
        --v;
        ed[i] = {w, u, v};
    }
    int q;
    cin >> q;
    vector<array<int, 3>> qq;
    for (int i = 0; i < q; ++i) {
        int t, u, w;
        cin >> t >> u >> w;
        --u;
        qq.push_back({t, u, w});
    }
    constexpr int K = 1100;
    vector<int> ans(q, -1);
    for (int i = 0; i < q; i += K) {
        vector<bool> bad(m);
        vector<int> rebra;
        rebra.reserve(K);
        auto edd = ed;
        vector<array<int, 4>> ev;
        ev.reserve(K + m);
        for (int j = i; j < min(q, i + K); ++j) {
            auto [t, u, w] = qq[j];
            if (t == 1) {
                bad[u] = 1;
                edd[u][0] = w;
                rebra.push_back(j);
            } else {
                ev.push_back({w, 0, u, j});
            }
        }
        sort(rebra.begin(), rebra.end(), [&](int i, int j) {
            return qq[i][1] < qq[j][1] || (qq[i][1] == qq[j][1] && i < j);
        });
        // for (int i : rebra) {
        //     cout << qq[i][1] + 1 << " " << qq[i][2] << "\n";
        // }
        for (int j = 0; j < m; ++j) {
            auto [w, u, v] = ed[j];
            if (!bad[j]) {
                ev.push_back({w, 1, u, v});
            }
        }
        sort(ev.rbegin(), ev.rend());
        DSU d(n);
        for (auto [w, t, u, v] : ev) {
            if (t == 0) {
                int kek = d.rb.size();
                // if (v == 11) {
                //     cout << "huy\n";
                // }
                for (int k = 0; k < (int) rebra.size();) {
                    int bebra = k;
                    int ves = -1;
                    while (bebra < (int) rebra.size() && qq[rebra[bebra]][1] == qq[rebra[k]][1]) {
                        if (rebra[bebra] < v) {
                            ves = qq[rebra[bebra]][2];
                        }
                        ++bebra;
                    }
                    int nomer = qq[rebra[k]][1];
                    if (ves == -1) {
                        ves = ed[nomer][0];
                    }
                    // debug(d.sz[d.get(u)]);
                    if (w <= ves) {
                        // if (v == 11) {
                        //     d.print();
                        // }
                        d.unite(ed[nomer][1], ed[nomer][2]);
                    }
                    k = bebra;
                }
                ans[v] = d.sz[d.get(u)];
                d.rollback(kek);
            } else {
                d.unite(u, v);
            }
        }
        ed = edd;
    }
    for (int i : ans) {
        if (i != -1) {
            cout << i << "\n";
        }
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27