Submission #1218284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218284		polarity	Bridges (APIO19_bridges)	C++20	59 / 100	3090 ms	7440 KiB

bridges

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

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#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;
    
    public:
        DSU(int size) : parents(size), sizes(size, 1){
            for (int i = 0; i < size; i++){
                parents[i] = i;
            }
        }

        int find(int x){
            return (parents[x] == x ? x : parents[x] = find(parents[x]));
        }

        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;
            return true;
        }

        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};
    }

    vector<vi> adj(n);
    DSU dsu(n);
    vector<bool> visited(n, false);
    rep(i, 0, q/rt + 1){
        vector<array<int, 3>> changes;
        vector<array<int, 4>> queries;
        int ac = 0;
        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;
                ac++;
            } else {
                queries.pb({b, a - 1, idx, ac});
            }
        }

        int nn = changes.size();
        
        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);

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

            vi checks;
            vi edges;
            rep (kk, nn - qac, changes.size()){
                array<int, 3> &change = changes[kk];

                int b = change[0];
                if (checked[b]) continue;
                checked[b] = true;
                checks.pb(b);
                if (change[1] >= w){
                    int fa = dsu.find(bridges[b][1]);
                    int fb = dsu.find(bridges[b][2]);

                    if (fa == fb) continue;

                    edges.pb(fa);
                    edges.pb(fb);

                    adj[fa].pb(fb);
                    adj[fb].pb(fa);
                }
            }

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

            vi vis;
            function<int(int)> dfs;
            dfs = [&](int x){
                if (visited[x]){
                    return 0;
                }

                visited[x] = true;
                vis.pb(x);

                int ans = 0;
                for (int node : adj[x]){
                    ans += dfs(node);
                }

                return ans + dsu.getSize(x);
            };

            ans[j] = dfs(dsu.find(a));

            for (int e : edges){
                adj[e].clear();
            }

            for (int v : vis){
                visited[v] = false;
            }
        }

        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