Submission #1244189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244189		yue_lai	timeismoney (balkan11_timeismoney)	C++20	45 / 100	6 ms	1156 KiB

timeismoney

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
struct e{
    long long int  x, y;
    long long int  cost;
    long long int  t,c;
};
bool cmp(e x, e y){
    return x.cost < y.cost;
}
long long int  n, m, x, y, c, todo, p[100000];
long long ans;
long long int  find(long long int  a){
    if (p[a] == a) return a;
    else {
        p[a] = find(p[a]);
        return p[a];
    }
}
vector <e> v;

long long int  ans1=0,ans2=0;

vector<pair<long long int ,long long int > >ch;
int main() {
    while (cin >> n >> m){
        todo = n-1;
        ans = 0;
        v.clear();
        for (long long int i = 0; i < n; i++){
            p[i] = i;
        }
        for (long long int  i = 0; i < m; i++){
        	long long int  o,p;
            cin >> x >> y >> o>>p;
            v.push_back({x, y, o*p,o,p});
        }
        
        
        sort(v.begin(), v.end(), cmp);
        
        
        for (long long int  i=0;i<v.size();i++){
            x = find(v[i].x);
            y = find(v[i].y);
            if (x == y) continue;
            else {
                p[y] = x;
                todo -= 1;
                ch.push_back(make_pair(v[i].x,v[i].y));
                ans1 += v[i].t;
                ans2 +=	v[i].c;
            }
        }
        if (todo == 0) cout << ans1 <<" "<<ans2<< "\n";
        else cout << "-1\n";
        for(long long int  i=0;i<ch.size();i++){
        	cout<<ch[i].first<<" "<<ch[i].second<<endl;
		}
    }
    return 0;
}


/*
5 7
 0 1 161 79
 0 2 161 15
 0 3 13 153
 1 4 142 183
 2 4 236 80
 3 4 40 241
 2 1 65 92

*/

• Subtask 1: 45 / 100