제출 #1363224

#제출 시각아이디문제언어결과실행 시간메모리
1363224NHristov다리 (APIO19_bridges)C++20
14 / 100
397 ms42436 KiB
#include <bits/stdc++.h>
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

using namespace std;

const int BLOCK = 2000, N = 5e4 + 5, M = 1e5 + 5;
int n, m;

struct DSU {
    int p[N], sz[N];
    vector<pair<int, int>> h;
    void init(int n) {
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            sz[i] = 1;
        }
    }
    int find(int u) {
        while (p[u] != 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;
        h.push_back({u, v});
    }
    int getSize() {
        return h.size();
    }
    void rollback(int tim) {
        while (h.size() > tim) {
            auto [u, v] = h.back();
            h.pop_back();
            sz[u] -= sz[v];
            p[v] = v;
        }
    }
    int compSize(int u) {
        return sz[find(u)];
    }
} dsu;

struct query {
    int type, u, v;
} queries[M];
struct ask {
    int id, s, w;
    vector<int> changedWeight;
};
struct edge {
    int u, v, w;
} e[M];

int pos[M], ans[M];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    set<pair<int, int>> ord;
    for (int i = 1; i <= m; i++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        ord.insert({e[i].w, i});
    }
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) cin >> queries[i].type >> queries[i].u >> queries[i].v;
    for (int i = 1; i <= m; i++) pos[i] = -1;
    for (int l = 0; l < t; l += BLOCK) {
        int r = l + BLOCK - 1;
        if (r >= t) r = t - 1;
        vector<int> v, curr;
        for (int i = l; i <= r; i++) {
            if (queries[i].type == 1) {
                int id = queries[i].u;
                if (pos[id] == -1) {
                    pos[id] = v.size();
                    v.push_back(id);
                    curr.push_back(e[id].w);
                }
            }
        }
        vector<ask> asks;
        for (int i = l; i <= r; i++) {
            if (queries[i].type == 1) curr[pos[queries[i].u]] = queries[i].v;
            else {
                ask add;
                add.id = i;
                add.s = queries[i].u;
                add.w = queries[i].v;
                add.changedWeight = curr;
                asks.push_back(add);
            }
        }
        vector<int> normal;
        for (auto it = ord.rbegin(); it != ord.rend(); it++) {
            int id = it->second;
            if (pos[id] == -1) normal.push_back(id);
        }
        sort(asks.begin(), asks.end(), [&](const ask &x, const ask &y) {
            return x.w > y.w;
        });
        dsu.init(n);
        int ptr = 0;
        for (const ask &ask : asks) {
            while (ptr < normal.size() && e[normal[ptr]].w >= ask.w) {
                int id = normal[ptr];
                ptr++;
                dsu.unite(e[id].u, e[id].v);
            }
            int currSize = dsu.getSize();
            for (int i = 0; i < v.size(); i++) {
                if(ask.changedWeight[i] >= ask.w) {
                    int id = v[i];
                    dsu.unite(e[id].u, e[id].v);
                }
            }
            ans[ask.id] = dsu.compSize(ask.s);
            dsu.rollback(currSize);
        }
        for (int i = l; i <= r; i++) {
            if (queries[i].type == 1) e[queries[i].u].w = queries[i].v;
        }
        for (int i : v) pos[i] = -1;
    }
    for (int i = 0; i < t; i++) {
        if (queries[i].type == 2) cout << ans[i] << endl;
    }

    return 0;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…