Submission #1245334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245334		nh0902	Bridges (APIO19_bridges)	C++20	100 / 100	1654 ms	20228 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<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]);
}

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

void roll_back(int x) {
    while (store.size() > x) {
        int a = store.top();
        store.pop();
        sz[pa[a]] -= sz[a];
        pa[a] = 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";
}

vector<int> to_mrg[1001];

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

    prep();

    vector<bool> unchange(m + 1, true);

    int cur = 1;
    while (cur <= q) {

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

            } else {
                query.push_back(i);
            }
        }

        for (int i = cur; i <= min(cur + sq - 1, q); i ++) {
            if (t[i] == 1) d[pos[i]] = w[i];
            else {
                to_mrg[i - cur].clear();
                for (int j : update) {
                    if (d[pos[j]] >= w[i]) to_mrg[i - cur].push_back(pos[j]);
                }
            }
        }

        reset_dsu();
        sort(query.begin(), query.end(), [&](int a, int b) { return w[a] > w[b]; });

        for (int i = 1; i <= m; i ++) if (unchange[i]) unch_list.push_back(i);
        sort(unch_list.begin(), unch_list.end(),
		     [&](int a, int b) { return d[a] > d[b]; });

        int ptr = 0;

        for (int x : query) {

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

            while (ptr < unch_list.size() && d[unch_list[ptr]] >= w[x]) {
                mrg(u[unch_list[ptr]], v[unch_list[ptr]]);
                ptr ++;
            }

            int pre = store.size();
            for (int i : to_mrg[x - cur]) {
                mrg(u[i], v[i]);
            }

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

            roll_back(pre);

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

        }

        cur += sq;

        for (int i : update) unchange[pos[i]] = true;
    }

    for (int i = 1; i <= q; i ++) {
        if (t[i] == 2) cout << ans[i] << "\n";
    }

    return 0;
}

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