Submission #598235

#	Time	Username	Problem	Language	Result	Execution time	Memory
598235		Ozy	Bridges (APIO19_bridges)	C++17	14 / 100	99 ms	12588 KiB

bridges

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)

#define MAX 100000
#define u second.first
#define v second.second
#define w first.first
#define tipo first.second

#define padre first
#define tam second

lli n,m,q,a,b,c,t,x,y;
vector< pair<pair<lli,lli>, pair<lli,lli> > > orden;
pair<lli,lli> uf[MAX];
lli res[MAX+2];

lli sube(lli pos) {
    if (uf[pos].padre == pos) return pos;
    uf[pos].padre = sube(uf[pos].padre);
    return uf[pos].padre;
}

void une(lli a, lli b) {
    uf[b].padre = a;
    uf[a].tam += uf[b].tam;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    rep(i,1,m) {
        cin >> a >> b >> c;
        c = -c;
        orden.push_back({{c,1},{a,b} });
    }
    cin >> q;
    rep(Q,1,q) {
        cin >> t >> a >> b;
        b = -b;
        orden.push_back({ {b,2},{a,Q} });
    }
    sort(orden.begin(), orden.end());
    rep(i,1,n) uf[i] = {i,1};

    for (auto act : orden) {

        if (act.tipo == 1) {
            x = sube(act.u);
            y = sube(act.v);
            if (x != y) une(x,y);
        }
        else {
            x = sube(act.u);
            res[act.v] = uf[x].tam;
        }

    }

    rep(i,1,q) 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