Cod sursa(job #2453516)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 4 septembrie 2019 11:58:09
Problema Politie Scor 100
Compilator cpp-64 Status done
Runda Arhiva ICPC Marime 1.2 kb

#include <bits/stdc++.h>

#define maxN 250052



using namespace std;



ifstream fin("politie.in");

ofstream fout("politie.out");



typedef struct {

	int x,y,c,p;

} edge;

edge v[maxN*2];



int dad[maxN],n,m,d,p;

vector <int> res;

unordered_map <int, int> H;



bool mycmp(const edge &a, const edge &b) {

	if (a.c == b.c)

		return a.p < b.p;

	return a.c < b.c;

}



void readData() {

	fin >> n >> m >> d >> p;

	for (int i = 1 ; i <= m ; ++i)

		fin >> v[i].x >> v[i].y >> v[i].c >> v[i].p;

	for (int i = 1 ; i <= n ; ++i)

		dad[i] = i;

}



int getGroup(int x) {

	if (x == dad[x])

		return x;

	dad[x] = getGroup(dad[x]);

	return dad[x];

}



void makeGroup(int x, int y) {

	dad[getGroup(x)] = getGroup(y);

}



int main() {

	readData();

	sort(v+1,v+m+1,mycmp);

	for (int i = 1 ; i <= m ; ++i)

		if (getGroup(v[i].x) != getGroup(v[i].y)) {

			makeGroup(v[i].x, v[i].y);

			if (H[v[i].p] == 0) {

				++H[v[i].p];

				res.push_back(v[i].p);

			}

		}

	sort(res.begin(), res.end());

	for (int i = res.size() - 1 ; i >= 0 && p ; --p, --i)

		fout << res[i] << "\n";

	return 0;

}