Submission #721844

#	Time	Username	Problem	Language	Result	Execution time	Memory
721844		GrandTiger1729	Bridges (APIO19_bridges)	C++17	14 / 100	89 ms	3556 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> rt, sz;
    DSU(int n){
        rt.resize(n);
        iota(rt.begin(), rt.end(), 0);
        sz.resize(n, 1);
    }
    int find(int u){
        if (u == rt[u]) return u;
        return rt[u] = find(rt[u]);
    }
    bool same(int u, int v){
        return find(u) == find(v); 
    }
    void unite(int u, int v){
        u = find(u), v = find(v);
        if (u == v) return;
        rt[u] = v;
        sz[v] += sz[u];
    }
    int size(int u){
        return sz[find(u)];
    }
};

struct Edge {
    int u, v, w;
    Edge() = default;
    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w){} 
};
struct Query {
    int u, w, id;
    Query() = default;
    Query(int _u, int _w, int _i): u(_u), w(_w), id(_i){}
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    vector<Edge> ed(m);
    for (int i = 0; i < m; i++){
        int u, v, w; cin >> u >> v >> w;
        u--, v--;
        ed[i] = Edge(u, v, w);
    }
    sort(ed.begin(), ed.end(), [&](auto x, auto y){
        return x.w > y.w;
    });
    int q; cin >> q;
    vector<Query> qry(q);
    for (int i = 0; i < q; i++){
        int t, u, w; cin >> t >> u >> w;
        u--;
        qry[i] = Query(u, w, i);
    }
    sort(qry.begin(), qry.end(), [&](auto x, auto y){
        return x.w > y.w;
    });
    vector<int> ans(q);
    {
        DSU dsu(n);
        int i = 0;
        for (auto &[u, w, id]: qry){
            while (i < m && ed[i].w >= w){
                dsu.unite(ed[i].u, ed[i].v);
                i++;
            }
            ans[id] = dsu.size(u);
        }
    }
    for (auto &x: ans)
        cout << x << '\n';
    return 0;
}

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