Submission #1245164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245164		nh0902	Bridges (APIO19_bridges)	C++20	13 / 100	3096 ms	25140 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 5e4 + 10;

const int M = 1e5 + 10;

const int inf = 1e18;

int n, m, q, sq, k;

int u[M], v[M], d[M], cur_d[M];

int t[M], pos[M], w[M];

int pa[N], sz[N];

stack<pair<int, int>> store;

int ans[M];

void reset_dsu() {
    for (int i = 1; i <= n; i ++) {
        pa[i] = i;
        sz[i] = 1;
    }
    while (!store.empty()) store.pop();
}

int find_anc(int x) {
    return pa[x] == x ? x : find_anc(pa[x]);
}

int mrg(int a, int b) {
    a = find_anc(a);
    b = find_anc(b);
    if (a == b) return 0;
    if (sz[a] > sz[b]) swap(a, b);
    pa[a] = b;
    sz[b] += sz[a];
    store.push({a, b});
    return 1;
}

void roll_back() {
    if (store.empty()) return;
    auto [a, b] = store.top();
    store.pop();

    pa[a] = a;
    sz[b] -= sz[a];
}

void prep() {
    cin >> n >> m;
    sq = min((int) 1000, n);
    vector<int> V;
    for (int i = 1; i <= m; i ++) {
        cin >> u[i] >> v[i] >> d[i];
        V.push_back(d[i]);
    }
    cin >> q;
    for (int i = 1; i <= q; i ++) {
        cin >> t[i] >> pos[i] >> w[i];
        V.push_back(w[i]);
    }
    sort(V.begin(), V.end());
    map<int, int> mp;
    mp[V[0]] = 1;
    for (int i = 1; i < V.size(); i ++) {
        if (V[i] > V[i - 1]) mp[V[i]] = mp[V[i - 1]] + 1;
        k = max(k, mp[V[i]]);
    }

    for (int i = 1; i <= m; i ++) cur_d[i] = d[i] = mp[d[i]];
    for (int i = 1; i <= q; i ++) w[i] = mp[w[i]];

    //for (int i = 1; i <= m; i ++) cout << d[i] << "\n";
    //for (int i = 1; i <= q; i ++) cout << w[i] << "\n";
}

bool cmp_query(int i, int j) {
    return w[i] > w[j];
}

void solve() {
    vector<int> E[k + 1];
    vector<bool> unchange(m + 1, true);
    vector<int> change;
    int cur = 1;
    while (cur <= q) {
        for (int i = 1; i <= m; i ++) {
            E[d[i]].push_back(i);
        }

        vector<int> query;
        vector<int> update;
        for (int i = cur; i <= min(cur + sq - 1, q); i ++) {
            if (t[i] == 1) {
                update.push_back(i);
                unchange[pos[i]] = false;
                change.push_back(pos[i]);
            } else {
                query.push_back(i);
            }
        }

        reset_dsu();
        sort(query.begin(), query.end(), cmp_query);
        int cur_w = k;

        for (int x : query) {

            //cout << store.size() << "\n";

            while (cur_w >= w[x]) {
                for (int i : E[cur_w]) if (unchange[i]) {
                    mrg(u[i], v[i]);
                }
                cur_w --;
            }

            for (int i : update) {
                if (i > x) break;
                cur_d[pos[i]] = w[i];
            }

            int cnt = 0;
            for (int i : change) {
                if (cur_d[i] >= w[x]) cnt += mrg(u[i], v[i]);
            }

            ans[x] = sz[find_anc(pos[x])];

            while (cnt > 0) {
                roll_back();
                cnt --;
            }

            //cout << cnt << "\n\n";

            for (int i : update) {
                if (i > x) break;
                cur_d[pos[i]] = d[pos[i]];
            }
        }


        for (int i : update) {
            d[pos[i]] = cur_d[pos[i]] = w[i];
        }

        cur += sq;

        for (int i : change) unchange[i] = true;
        change.clear();
        for (int i = 1; i <= k; i ++) E[i].clear();
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();
    for (int i = 1; i <= q; i ++) {
        if (ans[i] > 0) cout << ans[i] << "\n";
    }

    return 0;
}

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