Submission #733013

#	Time	Username	Problem	Language	Result	Execution time	Memory
733013		boyliguanhan	Bridges (APIO19_bridges)	C++17	0 / 100	203 ms	4604 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
int p[100100], ans[100100], sz[100100];
int abp(int n) {return p[n]==n?n:p[n] = abp(p[n]);}
vector<tuple<int, int, int>> edges, queries;
void addedge(int a, int b){
    a = abp(a), b = abp(b);
    if(a!=b) {
        p[a] = b;
        sz[b]+=sz[a];
    }
}
int main() {
    iota(p, p+100100, 0);
    int n, m, q;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        sz[i] = 1;
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edges.push_back({c, a, b});
    }
    cin >> q;
    for(int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> a >> b;
        queries.push_back({b,a,i});
    }
    sort(queries.rbegin(), queries.rend());
    sort(edges.rbegin(), edges.rend());
    edges.push_back({0, 2e9, 2e9});
    int i = 0;
    for(int j = 0; j < q; j++) {
        while(edges[i] >= queries[j]) {
            addedge(get<1>(edges[i]), get<2>(edges[i]));
            i++;
        }
        ans[get<2>(queries[j])] = sz[abp(get<1>(queries[j]))];
    }
    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
}

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