Submission #992580

#	Time	Username	Problem	Language	Result	Execution time	Memory
992580		vladilius	Bridges (APIO19_bridges)	C++17	100 / 100	2369 ms	10616 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
#define arr3 array<int, 3>

struct dsu{
    vector<int> sz, p;
    vector<pair<int&, int>> ch;
    int n, S;
    dsu(int ns){
        n = ns;
        p.resize(n + 1);
        sz.resize(n + 1);
        for (int i = 1; i <= n; i++){
            p[i] = i;
            sz[i] = 1;
        }
    }
    int get(int v){
        if (p[v] == v) return v;
        return get(p[v]);
    }
    void unite(int x, int y){
        x = get(x); y = get(y);
        if (x == y) return;
        if (sz[x] > sz[y]) swap(x, y);
        ch.pb({p[x], p[x]});
        p[x] = y;
        ch.pb({sz[y], sz[y]});
        sz[y] += sz[x];
    }
    void check_point(){
        S = (int) ch.size();
    }
    void roll_back(){
        while (ch.size() != S){
            ch.back().ff = ch.back().ss;
            ch.pop_back();
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    struct data{
        int t, a, b;
    };
    
    struct edge{
        int u, v, w, i;
    };
    auto cmp = [&](edge& a, edge& b){
        return a.w > b.w;
    };
    
    int n, m; cin>>n>>m;
    vector<edge> t(m + 1);
    for (int i = 1; i <= m; i++){
        cin>>t[i].u>>t[i].v>>t[i].w;
        t[i].i = i;
    }

    int q; cin>>q;
    vector<data> qs(q + 1);
    for (int i = 1; i <= q; i++){
        cin>>qs[i].t>>qs[i].a>>qs[i].b;
    }
    vector<int> out(q + 1);
    int S = sqrt(q), l = 1, r = S;
    while (l <= q){
        sort(t.begin() + 1, t.end(), cmp);
        vector<int> act(m + 1);
        for (int i = 1; i <= m; i++){
            act[t[i].i] = i;
        }
        
        r = min(r, q);
        vector<array<int, 3>> ch, qq;
        vector<bool> used(m + 1), ban(m + 1);
        for (int i = l; i <= r; i++){
            auto &[tt, a, b] = qs[i];
            if (tt == 1){
                // a = act[a];
                ch.pb({act[a], b, i});
                used[act[a]] = 1;
            }
            else {
                qq.pb({b, a, i});
            }
        }
        
        auto upp = [&](int x){
            if (ch.empty() || ch[0][2] <= x) return -1;
            int l = 0, r = (int) ch.size() - 1;
            while (l + 1 < r){
                int m = (l + r) / 2;
                if (ch[m][2] > x){
                    l = m;
                }
                else {
                    r = m - 1;
                }
            }
            if (ch[r][2] > x) l = r;
            return l;
        };
        
        reverse(ch.begin(), ch.end());
        sort(qq.begin(), qq.end(), greater<arr3>());
        dsu T(n);
        vector<int> us, rem;
        int j = 1;
        for (auto &[w, s, ii]: qq){
            while (j <= m && t[j].w >= w){
                if (used[j]){
                    us.pb(j++);
                    continue;
                }
                T.unite(t[j].u, t[j].v);
                j++;
            }
            T.check_point();
            // ch
            for (int jj = upp(ii) + 1; jj < ch.size(); jj++){
                auto &[e, ww, pp] = ch[jj];
                if (ban[e]) continue;
                ban[e] = 1;
                rem.pb(e);
                if (ww < w) continue;
                T.unite(t[e].u, t[e].v);
            }
            // us
            for (int e: us){
                if (!ban[e]){
                    T.unite(t[e].u, t[e].v);
                }
            }
            out[ii] = T.sz[T.get(s)];
            
            for (int e: rem) ban[e] = 0;
            rem.clear();
            T.roll_back();
        }
        reverse(ch.begin(), ch.end());
        for (auto &[e, ww, pp]: ch){
            t[e].w = ww;
        }
        l += S; r += S;
    }
    
    for (int i = 1; i <= q; i++){
        if (qs[i].t == 1) continue;
        cout<<out[i]<<"\n";
    }
}

Compilation message (stderr)

bridges.cpp: In member function 'void dsu::roll_back()':
bridges.cpp:41:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         while (ch.size() != S){
      |                ~~~~~~~~~~^~~~
bridges.cpp: In function 'int main()':
bridges.cpp:132:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |             for (int jj = upp(ii) + 1; jj < ch.size(); jj++){
      |                                        ~~~^~~~~~~~~~~

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