제출 #1013177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1013177		vjudge1	시간이 돈 (balkan11_timeismoney)	C++11	45 / 100	3 ms	856 KiB

timeismoney

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define f first
#define s second
using namespace std;
int mod = 1e9+7;
ll inf = 1e18+5;
int n,m,size[205],link[205],reza1,reza2;
vector<pair<pii,pii>> putovi;
vector<pii> reza;
int find(int a){
	if(link[a]==a)return a;
	return link[a] = find(link[a]);
}

bool same(int a,int b){
	return (find(a)==find(b));
}


int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for(int i = 0; i<205; i++){size[i]=1; link[i]=i;}	
	cin>>n>>m;
	for(int i = 0; i<m; i++){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		putovi.push_back({{c,d},{a,b}});
	}
	sort(putovi.begin(),putovi.end());
	for(auto z : putovi){
		int a = z.s.f;
		int b = z.s.s;
		if(same(a,b))continue;
		a = find(a);
		b = find(b);
		if(size[a]>size[b])swap(a,b);
		//size od a je manji od size od b
		size[b]+=size[a];
		link[b]=a;
		reza1+=z.f.f;
		reza2+=z.f.s;
		reza.push_back({z.s.f,z.s.s});
	}
	cout<<reza1<<" "<<reza2<<endl;
	for(auto z : reza)cout<<z.f<<" "<<z.s<<endl;
return 0;
}

• Subtask 1: 45 / 100