Submission #1098267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098267		vjudge1	Evacuation plan (IZhO18_plan)	C++17	0 / 100	106 ms	4336 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, 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, i};
    }

    int q;
    cin >> q;
    vector<tuple<int, int, int>> queries;
    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({w, s - 1, i});
        }
    }

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

    vector<int> answers(q, -1);
    UnionFind uf(n);
    int bridge_index = 0;

    for (auto [w, s, query_index] : queries) {
        while (bridge_index < m && get<0>(bridges[bridge_index]) >= w) {
            int u = get<1>(bridges[bridge_index]);
            int v = get<2>(bridges[bridge_index]);
            uf.unionSets(u, v);
            bridge_index++;
        }
        int root_s = uf.find(s);
        int reachable = 0;
        for (int i = 0; i < n; ++i) {
            if (uf.find(i) == root_s) reachable++;
        }
        answers[query_index] = reachable;
    }

    for (int ans : answers) {
        if (ans != -1) cout << ans << endl;
    }

    return 0;
}

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