Submission #1058356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058356		BF001	Bridges (APIO19_bridges)	C++17	100 / 100	2689 ms	111804 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
 
#define N 50005
#define fi first
#define se second
#define M 100005

typedef pair<int, int> ii;

struct pi{
    int u, v, w;
    bool operator < (pi& o){
        return w < o.w;
    }
};

struct qri
{
    int typ, idx, w;
};

int n, m, q, par[N], siz[N], blsiz, vs[M], res[M];
qri qr[M];
pi eg[M];
vector<pi> olde;
vector<int> newe;
vector<pi> getres;
vector<ii> check[M];
vector<ii> st; 

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

void unin(int u, int v){
    u = find(u);
    v = find(v);
    if (u == v) return;
    if (siz[u] < siz[v]) swap(u, v);
    par[v] = u;
    siz[u] += siz[v];
    st.push_back({u, v});
}

void roolback(int si){
    while ((int) st.size() > si){
        int u = st.back().fi;
        int v = st.back().se;
        siz[u] -= siz[v];
        par[v] = v;
        st.pop_back();
    } 
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    cin >> n >> m;
    for (int i = 1; i <= m; i++){
        cin >> eg[i].u >> eg[i].v >> eg[i].w;
    }

    cin >> q;
    blsiz = sqrt(q);
    for (int i = 1; i <= q; i++){
        res[i] = -1;
        cin >> qr[i].typ >> qr[i].idx >> qr[i].w;
    }

    for (int l = 1; l <= q; l += blsiz){
        int r = min(q, l + blsiz - 1);
        for (int i = l; i <= r; i++){
            if (qr[i].typ == 2){
                getres.push_back({qr[i].idx, i, qr[i].w});
                continue;
            }
            if (!vs[qr[i].idx]){
                vs[qr[i].idx] = 1;
                newe.push_back(qr[i].idx);
            }
        }
        for (int i = 1; i <= n; i++){
            par[i] = i;
            siz[i] = 1;
        }
        for (int i = 1; i <= m; i++){
            if (!vs[i]){
                olde.push_back({eg[i].u, eg[i].v, eg[i].w});
            }
        }
        sort(olde.begin(), olde.end());
        for (int i = l; i <= r; i++){
            if (qr[i].typ == 1){
                eg[qr[i].idx].w = qr[i].w;
                continue;
            }
            for (auto x : newe){
                if (eg[x].w >= qr[i].w){
                    check[i].push_back({eg[x].u, eg[x].v});
                }
            }
        }
        sort(getres.begin(), getres.end());
        int pos = (int) olde.size();
        for (int i = (int) getres.size() - 1; i >= 0; i--){
            auto x = getres[i];
            while (pos > 0 && olde[pos - 1].w >= x.w){
                pos--;
                unin(olde[pos].u, olde[pos].v);
            }
            int si = (int) st.size();
            for (auto v : check[x.v]){
                unin(v.fi, v.se);
            }
            res[x.v] = siz[find(x.u)];
            roolback(si);
            check[x.v].clear();
        }
        olde.clear();
        getres.clear();
        for (auto x : newe) vs[x] = 0;
        newe.clear();
        st.clear();
    }
 
    for (int i = 1; i <= q; i++){
        if (res[i] != -1){
            cout << res[i] << "\n";
        }
    }

    return 0;
}

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