Submission #1098266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098266		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	116 ms	6596 KiB

plan

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

class UnionFind {
public:
    vector<int> parent, rank;
    UnionFind(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int u) {
        if (parent[u] != u) parent[u] = find(parent[u]);
        return parent[u];
    }
    void unionSets(int u, int v) {
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) {
            if (rank[root_u] > rank[root_v]) parent[root_v] = root_u;
            else if (rank[root_u] < rank[root_v]) parent[root_u] = root_v;
            else {
                parent[root_v] = root_u;
                ++rank[root_u];
            }
        }
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    vector<tuple<int, int, int>> bridges(m);
    for (int i = 0; i < m; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        bridges[i] = {d, u - 1, v - 1};
    }

    int q;
    cin >> q;
    vector<pair<int, int>> queries;
    vector<pair<int, int>> updates;
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int b, r;
            cin >> b >> r;
            get<0>(bridges[b - 1]) = r;
        } else {
            int s, w;
            cin >> s >> w;
            queries.push_back({s - 1, w});
        }
    }

    sort(bridges.rbegin(), bridges.rend());

    for (auto [s, w] : queries) {
        UnionFind uf(n);
        for (auto [d, u, v] : bridges) {
            if (d <= w) uf.unionSets(u, v);
        }
        int reachable = 0;
        for (int i = 0; i < n; ++i) {
            if (uf.find(i) == uf.find(s)) ++reachable;
        }
        cout << reachable << endl;
    }

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 12
• Subtask 4: 0 / 19
• Subtask 5: 0 / 46