Cod sursa(job #2831329)

Utilizator RamanujanNeacsu Mihnea Ramanujan Data 11 ianuarie 2022 10:18:25
Problema Politie Scor 0
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 1.21 kb
#include <fstream>
#include<set>
#include<algorithm>
#define MAXN 200000
using namespace std;
ifstream fin("politie.in");
ofstream fout("politie.out");
int sefi[MAXN];
set<int> s;
struct edge{
    int x, y, cost, danger;
}a[MAXN];
bool compareTwoEdges(edge a , edge b){
    if(a.cost==b.cost){
        return a.danger<b.danger;
    }
    return a.cost<b.cost;
}
int find(int i){
    if(i==sefi[i])
       return sefi[i];
    return sefi[i]=find(sefi[i]);
}
void unify(int x, int y){
    int setX=find(x), setY=find(y);
    sefi[setX]=setY;
}
void minSpanningTree(int n, int e){
    for(int i=1; i<=n; i++){
       sefi[i]=i;
    }
    for(int i=0; i<e; i++){
        if(find(a[i].x)!=find(a[i].y)){
           unify(a[i].x, a[i].y);
           s.insert(-a[i].danger);
        }
    }
}
int main()
{
    int n, m, d, p; fin>>n>>m>>d>>p;
    for(int i=0; i<m; i++){
        fin>>a[i].x>>a[i].y>>a[i].cost>>a[i].danger;
    }
    sort(a, a+m, compareTwoEdges);
    minSpanningTree(n, m);
    int solsOut=0;
    set<int>::iterator it;
    for(it=s.begin(); it!=s.end(); it++){
        if(solsOut<p){
           fout<<-(*it)<<"\n";
           solsOut++;
        }
    }
    return 0;
}