Submission #142552

#	Time	Username	Problem	Language	Result	Execution time	Memory
142552		imeimi2000	Bridges (APIO19_bridges)	C++17	100 / 100	2824 ms	12628 KiB

bridges

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#define fs first
#define se second

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

const int B = 1000;
int n, m, q;
int U[100001], V[100001], D[100001];
int CD[100001];
int T[100001], X[100001], Y[100001];
int ans[100001];

struct union_find {
    int par[100001];
    int sz[100001];
    vector<int> op;
    void init() {
        op.clear();
        for (int i = 1; i <= n; ++i) {
            par[i] = 0;
            sz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x]) return find(par[x]);
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return 0;
        if (sz[x] < sz[y]) swap(x, y);
        par[y] = x;
        sz[x] += sz[y];
        op.push_back(y);
        return 1;
    }
    void restore() {
        int y = op.back();
        op.pop_back();
        int x = par[y];
        par[y] = 0;
        sz[x] -= sz[y];
    }
    int size() {
        return op.size();
    }
} uf;

bool ch[100001];
vector<int> cv;
set<pii> es;
void process_pre(int qs, int qe) {
    for (int i = qs; i <= qe; ++i) {
        if (T[i] == 1) {
            ch[X[i]] = 1;
            cv.push_back(X[i]);
        }
    }
    uf.init();
    sort(cv.begin(), cv.end());
    cv.erase(unique(cv.begin(), cv.end()), cv.end());
}

void process_ans(int qs, int qe) {
    vector<pii> qv;
    for (int i = qs; i <= qe; ++i) {
        if (T[i] == 2) qv.emplace_back(Y[i], i);
    }
    sort(qv.begin(), qv.end());
    auto it = es.begin();
    for (pii i : qv) {
        while (it != es.end() && it->fs <= i.fs) {
            int j = it->se;
            if (!ch[j])
                uf.merge(U[j], V[j]);
            ++it;
        }
        int sz = uf.size();
        for (int j : cv) CD[j] = D[j];
        for (int j = qs; j <= qe; ++j) {
            if (j > i.se) break;
            if (T[j] == 1) CD[X[j]] = Y[j];
        }
        for (int j : cv) if (CD[j] <= i.fs)
            uf.merge(U[j], V[j]);
        ans[i.se] = uf.sz[uf.find(X[i.se])];
        while (sz < uf.size()) uf.restore();
    }
}

void process_end(int qs, int qe) {
    for (int i = qs; i <= qe; ++i) {
        if (T[i] == 1) {
            es.erase(pii(D[X[i]], X[i]));
            D[X[i]] = Y[i];
            es.emplace(D[X[i]], X[i]);
            ch[X[i]] = 0;
        }
    }
    cv.clear();
}

const int inf = 1e9;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> U[i] >> V[i] >> D[i];
        D[i] = inf - D[i];
        es.emplace(D[i], i);
    }
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> T[i] >> X[i] >> Y[i];
        Y[i] = inf - Y[i];
    }
    for (int g = 0; ; ++g) {
        int qs = g * B + 1, qe = (g + 1) * B;
        qe = min(qe, q);
        if (qs > qe) break;
        process_pre(qs, qe);
        process_ans(qs, qe);
        process_end(qs, qe);
    }
    for (int i = 1; i <= q; ++i) {
        if (T[i] == 2) printf("%d\n", ans[i]);
    }
    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