Submission #934046

#	Time	Username	Problem	Language	Result	Execution time	Memory
934046		Lemser	Bridges (APIO19_bridges)	C++14	14 / 100	84 ms	16688 KiB

bridges

#include <bits/stdc++.h>
#define endl '\n'
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define fore(i,l,r) for(int i = l; i < r;i++)
#define forex(i,r,l) for(int i = r; i>= l;i--)
#define fo(i,n) fore(i,0,n)
#define ffo(i,n) forex(i,n-1,0)
#define lsb(x) x&(-x)
using namespace std;
using ii = pair<int,int>;using ll = long long; using ull = unsigned long long;
using vi = vector<int>;
const int N = 1e5+7;
int res[N];
vector<ii> graph[N];
struct evento{
    int peso, a,b,i;
};
vector<evento> eventos;
bool ord(evento a, evento b){
    if(a.peso == b.peso)return a.b > b.b; // las updates primero 
    return a.peso > b.peso;
}
struct dsu{
    vi pa,nh; int gru;
    dsu(int n){
        pa.resize(n+1);
        nh.resize(n+1);
        gru = n;
        fo(i,n+1){
            pa[i] = i;nh[i] = 1;
        }
    }
    int find(int i ){
        if(pa[i] == i) return i;
        return pa[i] = find(pa[i]);
    }
    void unite(int a, int b ){
        a = find(a); b = find(b);
        if(a == b)return;
        if(nh[a] < nh[b])swap(a,b);
        pa[b]=a;
        nh[a]+=nh[b];gru--;
    }
    int tam(int a ){
        return nh[find(a)];
    }
};
struct query{
    int op,a,b;
};
int main(){cin.tie(0)->sync_with_stdio(0);
    int n,m; cin >> n >> m;
    fo(i,m){
        int a,b,w; cin >> a >> b >> w;
        eventos.pb({w,a,b,i});
        graph[a].pb({b,w});
        graph[b].pb({a,w});
    }
    int q; cin >> q;
    int con = 0;
    vector<query> queries;
    fo(i,q){
        int op; cin >> op;
        if(op==2) con++;
        int nodo, peso;
        cin >> nodo >> peso;
        queries.pb({op,nodo,peso});
        eventos.pb({peso, nodo,-1,i});
    }
    if(con == q){// No hay updates
        sort(all(eventos), ord);
        dsu ami(n);
        for(auto e : eventos){
            if(e.b == -1){
                res[e.i] = ami.tam(e.a);
            }else{
                ami.unite(e.a,e.b);
            }
        }
        fo(i,q)cout << res[i] << endl;
    }else if (m==n-1){

    }else{

    }
}

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