Submission #434708

#	Time	Username	Problem	Language	Result	Execution time	Memory
434708		Mounir	Bridges (APIO19_bridges)	C++14	14 / 100	451 ms	14216 KiB

bridges

#include <bits/stdc++.h>
#define chmax(x, v) x = max(x, v)
#define pii pair<int, int>
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define int long long
using namespace std;
     
const int N = 1e6;
 
struct Arete {
    int noeud, voisin, poids;
 
    bool operator < (const Arete &autre) const {
        if (poids != autre.poids)
            return poids > autre.poids;
        if (voisin != autre.voisin)
            return voisin > autre.voisin;
        return noeud < autre.noeud;
    }
};
 
int ens[N], taille[N];
 
int getEns(int noeud){
    if (ens[noeud] != noeud)
        ens[noeud] = getEns(ens[noeud]);
    return ens[noeud];
}
 
int ans[N];
 
     
signed main(){
    int nNoeuds, nAretes; cin >> nNoeuds >> nAretes;
    vector<Arete> aretes(nAretes);
    for (Arete& arete : aretes)
        cin >> arete.noeud >> arete.voisin >> arete.poids;
    for (int noeud = 1; noeud <= nNoeuds; ++noeud){
        ens[noeud] = noeud;
        taille[noeud] = 1;
    }
 
    int nReqs; cin >> nReqs;
    for (int iReq = 0; iReq < nReqs; ++iReq){
        int typeReq, noeud, poids; cin >> typeReq >> noeud >> poids;
        aretes.pb({noeud, -iReq, poids});
    }
 
    sort(all(aretes));
    for (Arete& arete : aretes){
        if (arete.voisin > 0){
            arete.noeud = getEns(arete.noeud), arete.voisin = getEns(arete.voisin);
            if (arete.noeud != arete.voisin){
                ens[arete.noeud] = arete.voisin;
                taille[arete.voisin] += taille[arete.noeud];
            }
        }
        else {
            arete.voisin = -arete.voisin;
            ans[arete.voisin] = taille[getEns(arete.noeud)];
        }
    }
 
    for (int iReq = 0; iReq < nReqs; ++iReq)
        cout << ans[iReq] << 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