제출 #1294471

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294471		notisora	다리 (APIO19_bridges)	C++20	27 / 100	3093 ms	5644 KiB

bridges

///NotIsora
///This is my last dance
#include<bits/stdc++.h>
#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
///#define int long long

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 t, a, b, id;
} qs[M];

int n, m, q;
int p[N], sz[N];
int ans[M];
bool chg[M];
vector<pair<int, int>> hist;

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

void rollback(int snapshot) {
    while (hist.size() > snapshot) {
        int v = hist.back().fi;
        int u = hist.back().se;
        hist.pop_back();
        sz[u] -= sz[v];
        p[v] = v;
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
     //freopen("i.INP","r",stdin);

    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;
    }

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

        vector<int> chg_idx;
        vector<int> q2;
        for (int i = l; i <= r; ++i) {
            if (qs[i].t == 1) {
                chg[qs[i].a] = true;
                chg_idx.pb(qs[i].a);
            } else {
                q2.pb(i);
            }
        }

        sort(chg_idx.begin(), chg_idx.end());
        chg_idx.erase(unique(chg_idx.begin(), chg_idx.end()), chg_idx.end());

        vector<int> static_edges;
        for (int i = 1; i <= m; ++i) {
            if (!chg[i]) static_edges.pb(i);
        }
        sort(static_edges.begin(), static_edges.end(), [](int x, int y) {
            return edges[x].w > edges[y].w;
        });

        sort(q2.begin(), q2.end(), [](int x, int y) {
            return qs[x].b > qs[y].b;
        });

        for (int i = 1; i <= n; ++i) {
            p[i] = i;
            sz[i] = 1;
        }
        hist.clear();

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

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

            int snapshot = hist.size();

            for (int e_id : chg_idx) {
                int w_curr = edges[e_id].w;
                for (int i = l; i < q_idx; ++i) {
                    if (qs[i].t == 1 && qs[i].a == e_id) {
                        w_curr = qs[i].b;
                    }
                }

                if (w_curr >= 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) {
                edges[qs[i].a].w = qs[i].b;
                chg[qs[i].a] = false;
            }
        }
        for (int x : chg_idx) chg[x] = false;
    }

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

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