Submission #137299

#	Time	Username	Problem	Language	Result	Execution time	Memory
137299		mlyean00	Bridges (APIO19_bridges)	C++17	13 / 100	3058 ms	4436 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

struct disjoint_set {
    vector<int> parent, sz;

    disjoint_set(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int u) {
        if (u != parent[u]) u = find(parent[u]);
        return parent[u];
    }

    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        parent[u] = v;
        sz[v] += sz[u];
    }
};

struct query_1 {
    int t;
    int b, r;

    query_1(int t, int b, int r) : t(t), b(b), r(r) {}
};

struct query_2 {
    int t;
    int s, w;
    int ans = 0;

    query_2(int t, int s, int w) : t(t), s(s), w(w) {}

    bool operator<(query_2 const& other) {
        return w < other.w;
    }
};

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

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

    vector<int> u(m), v(m), d(m);
    for (int i = 0; i < m; ++i) {
        cin >> u[i] >> v[i] >> d[i];
        --u[i], --v[i];
    }

    int q;
    cin >> q;

    /* int blk_sz = ceil(sqrt(q)); */
    /* int blk_sz = q; */
    int blk_sz = 1;

    for (int i = 0; i < q; i += blk_sz) {
        vector<query_1> qu1;
        vector<query_2> qu2;
        for (int j = 0; j < min(blk_sz, q - i); ++j) {
            int t;
            cin >> t;
            if (t == 1) {
                int b, r;
                cin >> b >> r;
                --b;
                qu1.emplace_back(j, b, r);
                // Invalidate bridge
                d[b] = -abs(d[b]);
            } else if (t == 2) {
                int s, w;
                cin >> s >> w;
                --s;
                qu2.emplace_back(j, s, w);
            }
        }
        sort(qu2.rbegin(), qu2.rend());

        // Answer type 2 queries
        disjoint_set ds(n);
        for (query_2& q2 : qu2) {
            for (int j = 0; j < m; ++j) {
                if (d[j] >= q2.w) ds.merge(u[j], v[j]);
            }

            vector<pair<int, int>> edges;
            int src = ds.find(q2.s);
            vector<int> c {src};

            for (query_1 const& q1 : qu1) {
                if (q1.t <= q2.t) {
                    if (q1.r < q2.w) continue;
                    int u0 = ds.find(u[q1.b]);
                    int v0 = ds.find(v[q1.b]);
                    if (u0 != v0) {
                        edges.emplace_back(u0, v0);
                        c.push_back(u0);
                        c.push_back(v0);
                    }
                } else {
                    assert(d[q1.b] < 0);
                    if (-d[q1.b] < q2.w) continue;
                    int u0 = ds.find(u[q1.b]);
                    int v0 = ds.find(v[q1.b]);
                    if (u0 != v0) {
                        edges.emplace_back(u0, v0);
                        c.push_back(u0);
                        c.push_back(v0);
                    }
                }
            }

            // Coordinate compression
            sort(c.begin(), c.end());
            c.erase(unique(c.begin(), c.end()), c.end());
            src = lower_bound(c.begin(), c.end(), src) - c.begin();

            // Graph construction
            vector<vector<int>> g(c.size());
            for (auto [u0, v0] : edges) {
                int u1 = lower_bound(c.begin(), c.end(), u0) - c.begin();
                int v1 = lower_bound(c.begin(), c.end(), v0) - c.begin();
                g[u1].push_back(v1);
                g[v1].push_back(u1);
            }

            // DFS
            stack<int> st;
            vector<bool> visited(g.size());

            st.push(src);
            visited[src] = true;

            while (!st.empty()) {
                int u0 = st.top();
                st.pop();
                for (int v0 : g[u0]) {
                    if (visited[v0]) continue;
                    visited[v0] = true;
                    st.push(v0);
                }
            }

            for (int j = 0; j < g.size(); ++j) {
                if (!visited[j]) continue;
                q2.ans += ds.sz[c[j]];
            }
        }

        // Apply changes from type 1 queries
        for (query_1 const& q1 : qu1) {
            d[q1.b] = q1.r;
        }

        // Print answers to type 2 queries
        sort(qu2.begin(), qu2.end(),
             [](query_2 const& q1, query_2 const& q2) { return q1.t < q2.t; });

        for (query_2 const& q2 : qu2) {
            cout << q2.ans << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:153:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < g.size(); ++j) {
                             ~~^~~~~~~~~~

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