Submission #772359

#	Time	Username	Problem	Language	Result	Execution time	Memory
772359		phoebe	Bridges (APIO19_bridges)	C++17	0 / 100	68 ms	23524 KiB

bridges

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

#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define FOR(i, n) for (int i = 0; i < n; i++)
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);

// solving ST 4: offline query 

const int maxn = 1e5 + 10;
int n, m, u[maxn], v[maxn], d[maxn], 
q, s[maxn], w[maxn], ans[maxn],
r[maxn], sz[maxn];
vector<pair<pii, int>> bruh; // {{val, is_query}, idx}

int find(int x){
    int start = x;
    while (x != r[x]) x = r[x];
    int root = x; x = start;
    while (r[x] != root){
        int temp = r[x];
        r[x] = root; x = temp;
    }
    return root;
}

void unite(int a, int b){
    a = find(a), b = find(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    sz[a] += sz[b]; r[b] = a;
}

signed main(){
    NYOOM;
    cin >> n >> m;
    fill(sz, sz + n + 1, 1);
    iota(r, r + n + 1, 0);
    FOR(i, m){
        cin >> u[i] >> v[i] >> d[i];
        bruh.PB({{-d[i], 0}, i});
    }
    cin >> q;
    FOR(i, q){
        int t; cin >> t; 
        if (t == 2){ // only type 2
            cin >> w[i] >> s[i];
            bruh.PB({{-w[i], 1}, i});
        }
    }
    sort(ALL(bruh));
    for (auto x : bruh){
        int is_query = x.F.S, idx = x.S;
        if (is_query){
            // cout << "answering query: node = " << s[idx] << ", weight = " << w[idx] << endl;
            ans[idx] = sz[find(s[idx])];
        }
        else{
            // cout << "adding edge from " << u[idx] << " to " << v[idx] << endl;
            unite(u[idx], v[idx]);
        }
        // FOR(i, n) cout << sz[find(i + 1)] << ' '; cout << endl;
    }
    FOR(i, q) cout << ans[i] << endl;
}

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