Submission #1256714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256714		bbldrizzy	Bridges (APIO19_bridges)	C++20	100 / 100	2029 ms	38236 KiB

bridges

#include <bits/stdc++.h>
#include <ios>
#include <iostream>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define f first
#define s second
const int MOD = 1e9+7;
const ll inf = 4*1e18;
const int mx = 1e5+5;
int B = 700;
int u[mx], v[mx], d[mx];
int t[mx], x[mx], y[mx];
int pr[mx], sz[mx];
int ans[mx];
vector<int> ops;

int find(int a) {
    while (pr[a] != a) a = pr[a]; return a;
}

void merge(int xr, int yr) {
    xr = find(xr);
    yr = find(yr);
    if (xr == yr) return;
    if (sz[xr] > sz[yr]) swap(xr, yr);
    ops.push_back(xr);
    sz[yr] += sz[xr];
    pr[xr] = pr[yr];
}

bool con(int x, int y) {
    return find(x) == find(y);
}

void rem(int x) {
    while (ops.size() > x) {
        int t = ops.back(); ops.pop_back();
        sz[pr[t]] -= sz[t];
        pr[t] = t;
    }
}

bool cmp(int a, int b) {
    return d[a] > d[b];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> d[i];
    }
    int q; cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> t[i] >> x[i] >> y[i];
    }
    for (int i = 1; i <= q; i += B) {
        int r = min(q+1, i+B);
        vector<bool> chg(m+1);
        vector<vector<int>> add(B);
        vector<int> unchg;
        vector<int> upd;
        iota(pr, pr+n+5, 0);
        fill(sz, sz+n+5, 1);
        for (int j = i; j < r; j++) {
            if (t[j] == 1) {
                chg[x[j]] = true;
                upd.push_back(j);
            } 
        }
        for (int j = 1; j <= m; j++) {
            if (!chg[j]) unchg.push_back(j);
        }
        vector<int> ask;
        // for (int x: upd) {
        //     cout << x << "\n";
        // }
        // cout << "\n";
        for (int j = i; j < r; j++) {
            if (t[j] == 1) {
                d[x[j]] = y[j];
            } else {
                ask.push_back(j);
                for (int k: upd) {
                    if (d[x[k]] >= y[j]) add[j-i].push_back(x[k]);
                }
            }
        }
        // cout << "add:" << "\n";
        // for (int x: add[2]) {
        //     cout << x << "\n";
        // }
        // cout << "\n";
        // cout << "\n";
        sort(unchg.begin(), unchg.end(), cmp);
        sort(ask.begin(), ask.end(), [&](int a, int b) { return y[a] > y[b]; });
        // for (int x: ask) {
        //     cout << x << "\n";
        // }
        // cout << "\n";
        // cout << "\n";
        // for (int x: unchg) {
        //     cout << x << "\n";
        // }
        // cout << "\n";
        // cout << "\n";
        int ptr = 0;
        for (int j: ask) {
            while (ptr < unchg.size() && y[j] <= d[unchg[ptr]]) {
                merge(u[unchg[ptr]], v[unchg[ptr]]);
                ptr++;
            }
            // if (j == 3) {
            //     cout << "ptr: " << ptr << "\n";
            //     for (int k: add[j-i]) {
            //         cout << "k: " << k << "\n";
            //     }
            // }
            int prev_size = ops.size();
            for (int k: add[j-i]) {
                merge(u[k], v[k]);
            }
            // if (j == 3) {
            //     cout << "x[j], find(x[j]), sz[find]: " << x[j] << ", " << find(x[j]) << ", " << sz[find(x[j])] << "\n";
            // }
            ans[j] = sz[find(x[j])];
            rem(prev_size);
        }
    }
    // cout << "\n";
    for (int i = 1; i <= q; i++) {
        if (t[i]==2) cout << ans[i] << "\n";
    }
}

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