Submission #1125174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125174		adaawf	Bridges (APIO19_bridges)	C++20	100 / 100	1848 ms	8380 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int u[100005], v[100005], x[100005], y[100005], dd[100005], res[100005];
int p[50005], s[50005], ll = 1000;
vector<pair<int, int>> vv;
struct QUERY {
    int w, x, y, num;
} b[100005];
int Find(int x) {
    if (x == p[x]) return x;
    return Find(p[x]);
}
void Merge(int x, int y, int flag) {
    x = Find(x);
    y = Find(y);
    if (x == y) return;
    if (s[x] < s[y]) swap(x, y);
    s[x] += s[y];
    p[y] = x;
    if (flag == 1) vv.push_back({x, y});
}
void roll() {
    int x = vv.back().first, y = vv.back().second;
    vv.pop_back();
    p[y] = y;
    s[x] -= s[y];
}
bool cmp(QUERY aa, QUERY bb) {
    return aa.y > bb.y;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i] >> x[i];
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> b[i].w >> b[i].x >> b[i].y;
        b[i].num = i;
    }
    for (int i = 1; i <= q; i += ll) {
        int h = min(q, i + ll - 1);
        for (int j = 1; j <= m; j++) {
            dd[j] = 0;
            y[j] = x[j];
        }
        for (int j = 1; j <= n; j++) {
            p[j] = j;
            s[j] = 1;
        }
        vector<int> va;
        vector<QUERY> vb, vc;
        for (int j = i; j <= h; j++) {
            if (b[j].w == 1) {
                if (dd[b[j].x] == 0) {
                    dd[b[j].x] = 1;
                    va.push_back(b[j].x);
                }
            }
            else vc.push_back(b[j]);
        }
        for (int j = 1; j <= m; j++) {
            if (dd[j] == 0) {
                vb.push_back({u[j], v[j], x[j], 0});
            }
        }
        sort(vb.begin(), vb.end(), cmp);
        sort(vc.begin(), vc.end(), cmp);
        int j = 0;
        for (auto w : vc) {
            while (j < vb.size() && vb[j].y >= w.y) {
                Merge(vb[j].w, vb[j].x, 0);
                j++;
            }
            for (int j = i; j <= w.num; j++) {
                if (b[j].w == 1) {
                    x[b[j].x] = b[j].y;
                }
            }
            for (int ww : va) {
                if (x[ww] >= w.y) {
                    Merge(u[ww], v[ww], 1);
                }
            }
            res[w.num] = s[Find(w.x)];
            int h = vv.size();
            for (int j = 0; j < h; j++) roll();
            for (int ww : va) x[ww] = y[ww];
        }
        for (int j = i; j <= h; j++) {
            if (b[j].w == 1) {
                x[b[j].x] = b[j].y;
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        if (res[i] != 0) {
            cout << res[i] << '\n';
        }
    }
}

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