Submission #1111986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111986		Icelast	Bridges (APIO19_bridges)	C++17	100 / 100	1395 ms	13216 KiB

bridges

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct edge{
    ll u, v, w;
};
struct que{
    ll t, s, w, b, r, id;
};
struct DSU{
    int n;
    vector<int> pa, sz, history;
    DSU(int n) : n(n){
        pa.resize(n+1);
        sz.resize(n+1, 1);
        for(int i = 0; i <= n; i++){
            pa[i] = i;
        }
    };
    int find(int x){
        while(x != pa[x]){
            x = pa[x];
        }
        return x;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    bool merge(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(sz[x] < sz[y]) swap(x, y);
        pa[y] = x;
        history.push_back(y);
        sz[x] += sz[y];
        return true;
    }
    void rollback(int ver){
        while((int)history.size() > ver){
            int k = history.back();
            history.pop_back();
            sz[pa[k]] -= sz[k];
            pa[k] = k;
        }
    }
    int size(int x){
        return sz[find(x)];
    }
};
int B = 900;
void solve(){
    int n, m, Q;
    cin >> n >> m;
    vector<edge> e(m+1);
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
    }
    cin >> Q;
    vector<que> q(Q+1);
    for(int i = 1; i <= Q; i++){
        cin >> q[i].t;
        if(q[i].t == 1){
            cin >> q[i].b >> q[i].r;
        }else{
            cin >> q[i].s >> q[i].w;
        }
        q[i].id = i;
    }
    vector<bool> unchanged(m+1);
    vector<int> un_edges(m+1);
    iota(un_edges.begin()+1, un_edges.end(), 1);
    sort(un_edges.begin()+1, un_edges.end(), [&](int a, int b){return e[a].w > e[b].w;});
    vector<int> ans(Q+1, -1);
    for(int l = 1; l <= Q; l+=B){
        DSU dsu(n+1);
        fill(unchanged.begin(), unchanged.end(), true);
        int r = min(l+B-1, Q);
        for(int i = l; i <= r; i++){
            if(q[i].t == 1){
                unchanged[q[i].b] = false;
            }
        }
        vector<que> curq;
        for(int i = l; i <= r; i++){
            if(q[i].t == 2){
                curq.push_back(q[i]);
            }
        }
        sort(curq.begin(), curq.end(), [&](que a, que b){return a.w > b.w;});
        sort(un_edges.begin()+1, un_edges.end(), [&](int a, int b){return e[a].w > e[b].w;});
        vector<bool> done(m+1, false);
        int j = 1;
        for(auto it : curq){
            while(j <= m && e[un_edges[j]].w >= it.w){
                if(unchanged[un_edges[j]])
                    dsu.merge(e[un_edges[j]].u, e[un_edges[j]].v);
                j++;
            }
            int ver = dsu.history.size();
            for(int i = it.id-1; i >= l; i--){
                if(q[i].t == 1){
                    if(done[q[i].b]) continue;
                    if(q[i].r >= it.w){
                        dsu.merge(e[q[i].b].u, e[q[i].b].v);
                    }
                    done[q[i].b] = true;
                }
            }
            for(int i = it.id+1; i <= r; i++){
                if(q[i].t == 1 && e[q[i].b].w >= it.w && !done[q[i].b]){
                    dsu.merge(e[q[i].b].u, e[q[i].b].v);
                }
            }
            for(int i = it.id-1; i >= l; i--){
                if(q[i].t == 1){
                    done[q[i].b] = false;
                }
            }
            ans[it.id] = dsu.size(it.s);
            dsu.rollback(ver);
        }
        for(int i = l; i <= r; i++){
            if(q[i].t == 1){
                e[q[i].b].w = q[i].r;
            }
        }
    }
    for(int i = 1; i <= Q; i++){
        if(ans[i] == -1) continue;
        cout << ans[i] << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("main.inp", "r", stdin);
    //freopen("main.out", "w", stdout);
    solve();
}

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