Submission #706773

#	Time	Username	Problem	Language	Result	Execution time	Memory
706773		sharaelong	Bridges (APIO19_bridges)	C++17	0 / 100	3033 ms	26180 KiB

bridges

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

struct DisjointSet {
    int n;
    vector<int> parent, rank;
    vector<int> size;
    vector<tuple<int, int, int>> history;
    DisjointSet(int _n) : n(_n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        rank.resize(n, 0);
        size.resize(n, 1);
    }

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

    void merge(int u, int v) {
        // print(u, v);
        u = find(u); v = find(v);
        if (u == v) {
            history.push_back({ -1, -1, 0 });
            return;
        }
        if (rank[u] > rank[v]) swap(u, v);
        history.push_back({ u, v, 0 });
        parent[u] = v;
        size[v] += size[u];
        if (rank[u] == rank[v]) {
            ++rank[v];
            get<2>(history.back()) = 1;
        }
    }

    void undo() {
        // assert(!history.empty());
        if (history.empty()) exit(0);
        auto[u, v, c] = history.back();
        history.pop_back();
        if (u == -1) return;
        parent[u] = u;
        size[v] -= size[u];
        if (c == 1) rank[v]--;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pair<pii, vector<int>>> adj(m);
    for (int i=0; i<m; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        adj[i] = { { u, v }, { d } };
    }

    int q;
    cin >> q;
    vector<int> ans(q, -1);
    vector<tuple<int, int, int>> queries(q);
    for (auto&[t, a, b]: queries) cin >> t >> a >> b;

    vector<int> cc;
    for (int i=0; i<m; ++i) cc.push_back(adj[i].second.back());
    for (int i=0; i<q; ++i) cc.push_back(get<2>(queries[i])); // two query format is common for weight
    sort(cc.begin(), cc.end());
    cc.erase(unique(cc.begin(), cc.end()), cc.end());
    for (int i=0; i<m; ++i) adj[i].second.back() = lower_bound(cc.begin(), cc.end(), adj[i].second.back()) - cc.begin();
    for (int i=0; i<q; ++i) get<2>(queries[i]) = lower_bound(cc.begin(), cc.end(), get<2>(queries[i])) - cc.begin();
    
    DisjointSet dsu(n+1);
    vector<vector<int>> edges(cc.size());
    vector<int> updated(m, false);
    
    int block = sqrt(q) + 2; // block^2 >= q
    for (int i=0; i<block; ++i) {
        for (int j=0; j<edges.size(); ++j) edges[j].clear();
        vector<pii> block_queries;
        for (int j=i*block; j<min((i+1)*block, q); ++j) {
            if (get<0>(queries[j]) == 1) {
                int e = get<1>(queries[j])-1;
                updated[e] = true;
            } else {
                block_queries.push_back({ -get<2>(queries[j]), j });
            }
        }
        sort(block_queries.begin(), block_queries.end());

        for (int j=0; j<m; ++j) {
            if (!updated[j]) edges[adj[j].second.back()].push_back(j);
        }

        int curr_val = (int)edges.size()-1;
        for (auto[w, j]: block_queries) {
            int s = get<1>(queries[j]);
            w = -w;
            while (curr_val >= w) {
                for (int e: edges[curr_val]) {
                    auto[u, v] = adj[e].first;
                    dsu.merge(u, v);
                }
                curr_val--;
            }

            for (int k=i*block; k<j; ++k) {
                auto[t, b, r] = queries[k];
                if (t == 1) adj[b-1].second.push_back(r);
            }
            for (int k=i*block; k<min((i+1)*block, q); ++k) {
                auto[t, b, r] = queries[k];
                if (adj[b-1].second.back() >= w) {
                    auto[u, v] = adj[b-1].first;
                    dsu.merge(u, v);
                }
            }
            
            ans[j] = dsu.size[dsu.find(s)];

            // no needs for iterating k reversely
            for (int k=i*block; k<min((i+1)*block, q); ++k) {
                auto[t, b, r] = queries[k];
                if (adj[b-1].second.back() >= w) {
                    dsu.undo();
                }
            }
            for (int k=i*block; k<j; ++k) {
                auto[t, b, r] = queries[k];
                if (t == 1) adj[b-1].second.pop_back();
            }
        }
        for (int k=curr_val+1; k<edges.size(); ++k) {
            for (int _: edges[k]) dsu.undo();
        }

        for (int j=i*block; j<min((i+1)*block, q); ++j) {
            if (get<0>(queries[j]) == 1) {
                int e = get<1>(queries[j])-1;
                updated[e] = false;
            }
        }

        for (int j=i*block; j<min((i+1)*block, q); ++j) {
            auto[t, b, r] = queries[j];
            if (t == 1) adj[b-1].second.push_back(r);
        }
    }

    for (int i=0; i<q; ++i) {
        if (ans[i] != -1) cout << ans[i] << '\n';
    }
}

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

    solve();
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int j=0; j<edges.size(); ++j) edges[j].clear();
      |                       ~^~~~~~~~~~~~~
bridges.cpp:140:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |         for (int k=curr_val+1; k<edges.size(); ++k) {
      |                                ~^~~~~~~~~~~~~
bridges.cpp:141:22: warning: unused variable '_' [-Wunused-variable]
  141 |             for (int _: edges[k]) dsu.undo();
      |                      ^

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