Submission #1218282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218282		polarity	Bridges (APIO19_bridges)	C++20	59 / 100	3093 ms	5908 KiB

bridges

/**
 * Solution by Charles Ran (polarity.sh)
 * Date: 2025-06-14
 * Contest: APIO 2019
 * Problem: bridges
**/

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
using namespace std;

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

/** 
 * DS: Disjoint Set Union 
 * PURPOSE: Dynamically updates connectedness of graph by adding edges
 * TIME: amortized O(a(N)) to query
*/
class DSU {
    private: 
        vector<int> parents;
        vector<int> sizes;
        stack<int> updates;
    
    public:
        DSU(int size) : parents(size), sizes(size, 1){
            for (int i = 0; i < size; i++){
                parents[i] = i;
            }
        }

        int find(int x){
            int ans = x;
            while (parents[ans] != ans){
                ans = parents[ans];
            }
            return ans;
        }

        int getSize(int x){
            return sizes[find(x)];
        }

        bool unite(int a, int b){
            int parentA = find(a);
            int parentB = find(b);
            if (parentA == parentB){
                return false;
            }

            if (sizes[parentA] > sizes[parentB]){
                swap(parentA, parentB);
            }

            sizes[parentB] += sizes[parentA];
            parents[parentA] = parentB;
            updates.push(parentA);
            return true;
        }

        void rollback(int count){
            while (count-- && !updates.empty()){
                int last = updates.top();
                updates.pop();
                sizes[parents[last]] -= sizes[last];
                parents[last] = last;
            }
        }

        bool connected(int a, int b){
            return find(a) == find(b);
        }
};

array<int, 3> bridges[MAX_N];
array<int, 3> qs[MAX_N];
bool changed[MAX_N];
bool checked[50001];
int ans[MAX_N];

void solve(){
    int n, m; cin >> n >> m;

    rep(i, 0, m){
        int a, b, d; cin >> a >> b >> d;
        --a; --b;
        bridges[i] = {d, a, b};
    }
    
    int q; cin >> q;
    int rt = sqrt(q);
    rep(i, 0, q){
        int t, a, b; cin >> t >> a >> b;
        qs[i] = {t, a, b};
    }

    rep(i, 0, MAX_N/rt + 1){
        vector<array<int, 3>> changes;
        vector<array<int, 3>> queries;
        rep(j, 0, rt){
            int idx = i * rt + j;
            if (idx >= q) break;
            auto &[t, a, b] = qs[idx];
            if (t == 1){
                changes.pb({a - 1, b, idx});
                changed[a - 1] = true;
            } else {
                queries.pb({b, a - 1, idx});
            }
        }
        
        sort(queries.rbegin(), queries.rend());
        vector<array<int, 3>> sb;
        reverse(all(changes));
        rep(j, 0, m){
            if (!changed[j]){
                sb.pb(bridges[j]);
            } else {
                changes.pb({j, bridges[j][0], -1});
            }
        }
        sort(sb.rbegin(), sb.rend());
        int idx = 0;

        DSU dsu(n);
        for (auto &[w, a, j] : queries){
            while (idx < sb.size() && sb[idx][0] >= w){
                dsu.unite(sb[idx][1], sb[idx][2]);
                idx++;
            }

            int updated = 0;
            vi checks;
            for (array<int, 3> change : changes){
                if (change[2] >= j){
                    continue;
                }

                int b = change[0];
                if (checked[b]) continue;
                checked[b] = true;
                checks.pb(b);
                if (change[1] >= w){
                    if (dsu.unite(bridges[b][1], bridges[b][2])) {
                        updated++;
                    }
                }
            }

            for (int b : checks){
                checked[b] = false;
            }

            ans[j] = dsu.getSize(a);
            dsu.rollback(updated);
        }

        reverse(all(changes));

        for (array<int, 3> change : changes){
            bridges[change[0]][0] = change[1];
            changed[change[0]] = false;
        }
    }

    rep(i, 0, q){
        if (ans[i]){
            cout << ans[i] << endl;
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

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