Submission #722435

#	Time	Username	Problem	Language	Result	Execution time	Memory
722435		GrandTiger1729	Bridges (APIO19_bridges)	C++17	100 / 100	2734 ms	9764 KiB

bridges

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

struct DSU {
    vector<int> rt, sz;
    vector<int> stk;
    DSU(int n){
        rt.resize(n);
        iota(rt.begin(), rt.end(), 0);
        sz.resize(n, 1);
    }
    int find(int u){
        if (u == rt[u]) return u;
        return find(rt[u]);
    }
    bool same(int u, int v){
        return find(u) == find(v); 
    }
    void unite(int u, int v){
        u = find(u), v = find(v);
        if (u == v) return;
        if (sz[u] > sz[v])
            swap(u, v);
        rt[u] = v;
        sz[v] += sz[u];
        stk.push_back(u);
    }
    void undo(){
        int u = stk.back(), v = rt[u];
        stk.pop_back();
        sz[v] -= sz[u];
        rt[u] = u;
    }
    void rollback(){
        while (stk.size())
            undo();
    }
    void checkpoint(){
        stk.clear();
    }
    int size(int u){
        return sz[find(u)];
    }
};
struct Edge {
    int u, v, w, id;
    Edge() = default;
    Edge(int _u, int _v, int _w, int _i): u(_u), v(_v), w(_w), id(_i){} 
};
struct Event {
    int i, w, id;
    Event() = default;
    Event(int _i, int _w, int _id): i(_i), w(_w), id(_id){}
};
struct Query {
    int u, w, id;
    Query() = default;
    Query(int _u, int _w, int _i): u(_u), w(_w), id(_i){}
};

const int B = 500;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<Edge> ed(m);
    for (int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        ed[i] = Edge(u, v, w, i);
    }
    int q; cin >> q;
    vector<int> ans(q);
    for (int qq = 0; qq < q; ){
        int R = min(q, qq + B);
        vector<Event> evnt;
        vector<Query> qry;
        vector<int> vis(m);
        for (; qq < R; qq++){
            int t; cin >> t;
            if (t == 1){
                int i, w; cin >> i >> w;
                i--;
                evnt.emplace_back(i, w, qq);
                vis[i] = 1;
            }else{
                int u, w; cin >> u >> w;
                u--;
                qry.emplace_back(u, w, qq);
            }
        }
        reverse(evnt.begin(), evnt.end());
        vector<Edge> eed;
        for (int i = 0; i < m; i++){
            if (vis[i])
                evnt.emplace_back(i, ed[i].w, -1);
            else
                eed.push_back(ed[i]);
        }
        sort(eed.begin(), eed.end(), [&](auto x, auto y){
            return x.w > y.w;
        });
        sort(qry.begin(), qry.end(), [&](auto x, auto y){
            return x.w > y.w;
        });
        DSU dsu(n);
        int i = 0;
        for (auto &[u, w, id]: qry){
            while (i < eed.size() && eed[i].w >= w){
                dsu.unite(eed[i].u, eed[i].v);
                i++;
            }
            dsu.checkpoint();
            for (auto &[ii, ww, j]: evnt){
                if (j < id){
                    if (vis[ii] != -1 && ww >= w)
                        dsu.unite(ed[ii].u, ed[ii].v);
                    vis[ii] = -1;
                }
            }
            ans[id] = dsu.size(u);
            for (auto &[ii, ww, j]: evnt)
                if (j < id)
                    vis[ii] = 1;
            dsu.rollback();
        }
        reverse(evnt.begin(), evnt.end());
        for (auto [i, w, id]: evnt)
            if (id != -1)
                ed[i].w = w;
    }
    for (auto &x: ans)
        if (x != 0)
            cout << x << '\n';
    return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:108:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while (i < eed.size() && eed[i].w >= w){
      |                    ~~^~~~~~~~~~~~

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