Submission #598212

#	Time	Username	Problem	Language	Result	Execution time	Memory
598212		Ozy	Bridges (APIO19_bridges)	C++17	13 / 100	57 ms	724 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 1000
#define u second.first
#define v second.second
#define w first
#define padre first
#define tam second

lli n,m,q,a,b,c,t,x,y;
pair<lli, pair<lli,lli> > arr[MAX+2];
multiset< pair<lli, pair<lli,lli> > > orden;
pair<lli,lli> uf[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;
        arr[i] = {c, {a,b} };
        orden.insert({c,{a,b} });
    }
    orden.insert( {1, {0,0} });

    cin >> q;
    rep(Q,1,q) {

        cin >> t >> a >> b;
        b = -b;

        if (t == 1) {
            //cambio de peso en el limite
            auto it = orden.lower_bound(arr[a]);
            orden.erase(it);
            arr[a].w = b;
            orden.insert(arr[a]);
        }
        else {
            if (m == 0) {cout << 1 << endl; continue;}

            //query
            rep(i,1,n) uf[i] = {i,1};
            auto it = orden.begin();
            while (it != orden.end() && (*it).w <= b) {

                x = sube((*it).u);
                y = sube((*it).v);

                if (x != y) une(x,y);

                it++;
            }

            a = sube(a);
            cout << uf[a].tam << endl;
        }

    }
}

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