Submission #733016

#	Time	Username	Problem	Language	Result	Execution time	Memory
733016		boyliguanhan	Bridges (APIO19_bridges)	C++17	14 / 100	236 ms	10104 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100100
int n,m,q;
vector<pair<int, int>> v[MAXN];
int p[MAXN], sz[MAXN], res[MAXN];
vector<pair<int,pair<int, int>>> e;
vector<pair<pair<int, int>,int>> qu;
int abp(int n) {
    if (p[n] == n) return n;
    return p[n] = abp(p[n]);
}
void join(int a, int b) {
    a = abp(a);
    b = abp(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a,b);
        p[b] = a;
        sz[a] += sz[b];
    }
}
signed main() {
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int a,b,w;
        cin >> a >> b >> w;
        v[a].push_back({b,w});
        v[b].push_back({a,w});
        e.push_back({w,{a,b}});
    }
    sort(e.rbegin(), e.rend());
    cin >> q;
    for(int i = 0; i < q; i++) {
        int t,s,w;
        cin >> t >> s >> w;
        qu.push_back({{w,s},i});
    }
    for(int i = 1; i <= n; i++) {
        p[i] = i;
        sz[i] = 1;
    }
    sort(qu.rbegin(), qu.rend());
    int j = 0;
    for(int i = 0; i < q; i++) {
        int w = qu[i].first.first, s = qu[i].first.second, idx = qu[i].second;
        while (j < m && e[j].first >= w) {
            join(e[j].second.first, e[j].second.second);
            j++;
        }
        res[idx] = sz[abp(s)];
    }
    for(int i = 0; i < q; i++)
        cout << res[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