Submission #1187333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187333		inesfi	Bridges (APIO19_bridges)	C++20	14 / 100	53 ms	7336 KiB

bridges

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

#define endl "\n"
#define int long long

const int TAILLEMAXI=50*1000+2,INFINI=1000*1000*1000+2;
int pere[TAILLEMAXI],taillecompo[TAILLEMAXI];
vector<tuple<int,int,int>> aretes;
int rep[TAILLEMAXI*2];

int trouver(int a){
    if (pere[a]!=a){
        pere[a]=trouver(pere[a]);
    }
    return pere[a];
}

void unir(int a,int b){
    a=trouver(a);
    b=trouver(b);
    if (a!=b){
        taillecompo[a]+=taillecompo[b];
        pere[b]=pere[a];
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int nbnoeuds,nbaretes;
    cin>>nbnoeuds>>nbaretes;
    for (int i=0;i<nbaretes;i++){
        int a,b,p;
        cin>>a>>b>>p;
        aretes.push_back(make_tuple(-p,a,b));
    }
    int nbquest;
    cin>>nbquest;
    for (int i=0;i<nbquest;i++){
        int type,a,p;
        cin>>type>>a>>p;
        aretes.push_back({-p,INFINI+i,a});
    }
    sort(aretes.begin(),aretes.end());
    for (int i=1;i<=nbnoeuds;i++){
        pere[i]=i;
        taillecompo[i]=1;
    }
    for (auto i:aretes){
        if (get<1>(i)>=INFINI){
            rep[get<1>(i)-INFINI]=taillecompo[trouver(get<2>(i))];
        }
        else {
            unir(get<1>(i),get<2>(i));
        }
    }
    for (int i=0;i<nbquest;i++){
        cout<<rep[i]<<endl;
    }
    return 0;
}

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