Submission #1098332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098332		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	3051 ms	7172 KiB

bridges

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct B {
    int u, v, d;
};

struct Q {
    int t, x, y;
};

class UF {
public:
    vector<int> p, r, sz;

    UF(int n) {
        p.resize(n);
        r.resize(n, 0);
        sz.resize(n, 1);
        for (int i = 0; i < n; ++i) p[i] = i;
    }

    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    void unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            if (r[rx] > r[ry]) {
                p[ry] = rx;
                sz[rx] += sz[ry];
            } else if (r[rx] < r[ry]) {
                p[rx] = ry;
                sz[ry] += sz[rx];
            } else {
                p[ry] = rx;
                r[rx]++;
                sz[rx] += sz[ry];
            }
        }
    }

    int component_size(int x) {
        return sz[find(x)];
    }
};

int main() {
    int n, m;
    cin >> n >> m;

    vector<B> bs(m);
    for (int i = 0; i < m; ++i) {
        cin >> bs[i].u >> bs[i].v >> bs[i].d;
        bs[i].u--;
        bs[i].v--;
    }

    int q;
    cin >> q;
    vector<Q> qs(q);
    vector<int> res;

    for (int i = 0; i < q; ++i) {
        cin >> qs[i].t >> qs[i].x >> qs[i].y;
        qs[i].x--; // Сокращение на 1 в обоих случаях
    }

    for (int i = 0; i < q; ++i) {
        if (qs[i].t == 1) {
            bs[qs[i].x].d = qs[i].y;
        } else {
            int car_w = qs[i].y;
            int start = qs[i].x;
            UF uf(n);

            for (int j = 0; j < m; ++j) {
                if (bs[j].d >= car_w) {
                    uf.unite(bs[j].u, bs[j].v);
                }
            }

            res.push_back(uf.component_size(start));
        }
    }

    for (int r : res) {
        cout << r << endl;
    }

    return 0;
}

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