Submission #1294474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294474		notisora	다리 (APIO19_bridges)	C++20	27 / 100	3094 ms	8744 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 sq(x) (x)*(x)
#define ll long long
#define ld long double
#define el '\n'
#define pb push_back

using namespace std;

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

struct Edge {
    int u, v, w, id;
};

struct Query {
    int t, a, b, id;
};

int n, m, q;
Edge edges[M];
Query qs[M];
int ans[M];

int p[N], sz[N];
struct RollbackInfo {
    int u, v;
};
vector<RollbackInfo> history_st;

int last_updated_in_block[M];
int block_cnt = 0;

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.pb({v, u});
}

void rollback(int snapshot) {
    while (history_st.size() > snapshot) {
        int v = history_st.back().u;
        int u = history_st.back().v;
        history_st.pop_back();
        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;
    }

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> qs[i].t >> qs[i].a >> qs[i].b;
        qs[i].id = i;
    }

    vector<Edge> edge_list;
    edge_list.reserve(m);
    for(int i=1; i<=m; ++i) edge_list.pb(edges[i]);

    sort(edge_list.begin(), edge_list.end(), [](const Edge& a, const Edge& b){
        return a.w > b.w;
    });

    vector<int> current_w(m + 1);
    for(int i=1; i<=m; ++i) current_w[i] = edges[i].w;

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

        vector<int> dirty_indices;
        vector<int> q2_indices;

        for (int i = l; i <= r; ++i) {
            if (qs[i].t == 1) {
                if (last_updated_in_block[qs[i].a] != block_cnt) {
                    last_updated_in_block[qs[i].a] = block_cnt;
                    dirty_indices.pb(qs[i].a);
                }
            } else {
                q2_indices.pb(i);
            }
        }
        vector<Edge> static_edges;
        static_edges.reserve(m);
        for (auto& e : edge_list) {
            if (last_updated_in_block[e.id] != block_cnt) {
                static_edges.pb(e);
            }
        }

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

        for (int i = 1; i <= n; ++i) p[i] = i, sz[i] = 1;
        history_st.clear();

        int ptr = 0;
        for (int q_idx : q2_indices) {
            int w_req = qs[q_idx].b;

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

            int snapshot = history_st.size();

            for (int e_id : dirty_indices) {
                int w_real = current_w[e_id];
                for (int i = l; i < q_idx; ++i) {
                    if (qs[i].t == 1 && qs[i].a == e_id) {
                        w_real = qs[i].b;
                    }
                }

                if (w_real >= w_req) {
                    unite(edges[e_id].u, edges[e_id].v);
                }
            }

            ans[qs[q_idx].id] = sz[find(qs[q_idx].a)];

            rollback(snapshot);
        }

        for (int i = l; i <= r; ++i) {
            if (qs[i].t == 1) {
                current_w[qs[i].a] = qs[i].b;
            }
        }

        if (r < q) {
            vector<Edge> new_dirty_edges;
            for (int id : dirty_indices) {
                Edge e = edges[id];
                e.w = current_w[id];
                new_dirty_edges.pb(e);
            }
            sort(new_dirty_edges.begin(), new_dirty_edges.end(), [](const Edge& a, const Edge& b){
                return a.w > b.w;
            });

            edge_list.clear();
            int i = 0, j = 0;
            while (i < static_edges.size() && j < new_dirty_edges.size()) {
                if (static_edges[i].w >= new_dirty_edges[j].w) {
                    edge_list.pb(static_edges[i++]);
                } else {
                    edge_list.pb(new_dirty_edges[j++]);
                }
            }
            while (i < static_edges.size()) edge_list.pb(static_edges[i++]);
            while (j < new_dirty_edges.size()) edge_list.pb(new_dirty_edges[j++]);
        }
    }

    for (int i = 1; i <= q; ++i) {
        if (qs[i].t == 2) cout << ans[i] << 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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 14 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27