Submission #672726

#	Time	Username	Problem	Language	Result	Execution time	Memory
672726		jhnah917	Bridges (APIO19_bridges)	C++14	14 / 100	77 ms	4376 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
constexpr int B = 1000;

struct Edge{ int u, v, w; };
struct Query{ int op, s, w, idx; };

struct UnionFind{
    vector<int> p, s;
    UnionFind(int n) : p(n+1), s(n+1) {
        iota(p.begin(), p.end(), 0);
        fill(s.begin(), s.end(), 1);
    }
    int find(int v){ return v == p[v] ? v : p[v] = find(p[v]); }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u != v) p[u] = v, s[v] += s[u];
    }
    int size(int v){ return s[find(v)]; }
};

int N, M, Q, R[101010];
Edge E[101010];
Query Qry[101010];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++) cin >> E[i].u >> E[i].v >> E[i].w;
    cin >> Q;
    for(int i=1; i<=Q; i++) cin >> Qry[i].op >> Qry[i].s >> Qry[i].w, Qry[i].idx = i;
    sort(E+1, E+M+1, [](auto e1, auto e2){ return e1.w > e2.w; });
    sort(Qry+1, Qry+Q+1, [](auto q1, auto q2){ return q1.w > q2.w; });

    UnionFind U(N);
    for(int i=1, j=1; i<=Q; i++){
        while(j <= M && Qry[i].w <= E[j].w) U.merge(E[j].u, E[j].v), j++;
        R[Qry[i].idx] = U.size(Qry[i].s);
    }
    for(int i=1; i<=Q; i++) cout << R[i] << "\n";
}

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