Submission #1294477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294477		notisora	Bridges (APIO19_bridges)	C++20	100 / 100	589 ms	8772 KiB

bridges

///Lemmecode
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define modulo 1000000007
#define fi first
#define se second
#define ll long long
#define el '\n'
#define pb push_back

using namespace std;

const int N = 50005;
const int M = 100005;
const int B = 800;

struct Edge {
    int u, v, w, id;
} edges[M];

struct Query {
    int type, u, v, id;
} qs[M];

int n, m, q;
int ans[M];
int p[N], sz[N];

int e_ord[M];
bool is_dirty[M];
int dirty_ids[B + 5];
int cnt_dirty;

pair<int, int> history_st[M];
int h_top = 0;

int cache_w[B + 5][B + 5];

int find(int u) {
    while (u != p[u]) u = p[u];
    return u;
}

void unite(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return;
    if (sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    p[v] = u;
    history_st[h_top++] = {v, u};
}

void rollback(int snapshot) {
    while (h_top > snapshot) {
        int v = history_st[--h_top].fi;
        int u = history_st[h_top].se;
        sz[u] -= sz[v];
        p[v] = v;
    }
}

void run() {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
        edges[i].id = i;
        e_ord[i] = i;
    }

    sort(e_ord + 1, e_ord + m + 1, [](int i, int j) {
        return edges[i].w > edges[j].w;
    });

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> qs[i].type >> qs[i].u >> qs[i].v;
        qs[i].id = i;
    }

    for (int l = 1; l <= q; l += B) {
        int r = min(q, l + B - 1);
        cnt_dirty = 0;

        vector<int> q_indices;

        for (int i = l; i <= r; ++i) {
            if (qs[i].type == 1) {
                int eid = qs[i].u;
                if (!is_dirty[eid]) {
                    is_dirty[eid] = true;
                    dirty_ids[cnt_dirty++] = eid;
                }
            } else {
                q_indices.pb(i);
            }
        }

        for (int i = 0; i < cnt_dirty; ++i) cache_w[0][i] = edges[dirty_ids[i]].w;

        static int map_pos[M];
        for(int i=0; i<cnt_dirty; ++i) map_pos[dirty_ids[i]] = i;

        static int cur_w[M];
        for(int i=0; i<cnt_dirty; ++i) cur_w[dirty_ids[i]] = edges[dirty_ids[i]].w;

        for (int i = l; i <= r; ++i) {
            if (qs[i].type == 1) {
                cur_w[qs[i].u] = qs[i].v;
            } else {
                int q_local_idx = i - l;
                for (int k = 0; k < cnt_dirty; ++k) {
                    cache_w[q_local_idx][k] = cur_w[dirty_ids[k]];
                }
            }
        }

        static int clean_edges[M];
        int cnt_clean = 0;
        for (int i = 1; i <= m; ++i) {
            if (!is_dirty[e_ord[i]]) {
                clean_edges[cnt_clean++] = e_ord[i];
            }
        }

        sort(q_indices.begin(), q_indices.end(), [](int i, int j) {
            return qs[i].v > qs[j].v;
        });

        for (int i = 1; i <= n; ++i) p[i] = i, sz[i] = 1;
        h_top = 0;

        int ptr = 0;
        for (int idx : q_indices) {
            int w_req = qs[idx].v;

            while (ptr < cnt_clean && edges[clean_edges[ptr]].w >= w_req) {
                unite(edges[clean_edges[ptr]].u, edges[clean_edges[ptr]].v);
                ptr++;
            }

            int snapshot = h_top;

            int q_local_idx = idx - l;
            for (int k = 0; k < cnt_dirty; ++k) {
                if (cache_w[q_local_idx][k] >= w_req) {
                    int eid = dirty_ids[k];
                    unite(edges[eid].u, edges[eid].v);
                }
            }

            ans[qs[idx].id] = sz[find(qs[idx].u)];

            rollback(snapshot);
        }

        for (int i = l; i <= r; ++i) {
            if (qs[i].type == 1) edges[qs[i].u].w = qs[i].v;
        }

        sort(dirty_ids, dirty_ids + cnt_dirty, [](int i, int j) {
            return edges[i].w > edges[j].w;
        });
        int i = 0, j = 0, k = 1;
        while (i < cnt_clean && j < cnt_dirty) {
            if (edges[clean_edges[i]].w >= edges[dirty_ids[j]].w) {
                e_ord[k++] = clean_edges[i++];
            } else {
                e_ord[k++] = dirty_ids[j++];
            }
        }
        while (i < cnt_clean) e_ord[k++] = clean_edges[i++];
        while (j < cnt_dirty) e_ord[k++] = dirty_ids[j++];

        for (int x = 0; x < cnt_dirty; ++x) is_dirty[dirty_ids[x]] = false;
    }

    for (int i = 1; i <= q; ++i) {
        if (qs[i].type == 2) cout << ans[qs[i].id] << el;
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("i.INP","r",stdin);
    run();
    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