Submission #721885

#	Time	Username	Problem	Language	Result	Execution time	Memory
721885		GrandTiger1729	Bridges (APIO19_bridges)	C++17	13 / 100	3068 ms	2296 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);
    }
    int q; cin >> q;
    while (q--){
        int t; cin >> t;
        if (t == 1){
            int i, w; cin >> i >> w;
            i--;
            ed[i].w = w;
        }else{
            int u, w; cin >> u >> w;
            u--;
            DSU dsu(n);
            for (auto &[uu, vv, ww]: ed){
                if (ww >= w)
                    dsu.unite(uu, vv);
            }
            cout << dsu.size(u) << '\n';
        }
    }
    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