Submission #1186415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186415		FaresSTH	timeismoney (balkan11_timeismoney)	C++20	40 / 100	3 ms	584 KiB

timeismoney

#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define S second
#define F first
vector<array<int,3>>edg;
const int mxn=300;
int p[mxn],sz[mxn],s;
int f(int v){
    if(v!=p[v])p[v]=f(p[v]);
    return p[v];
}
void merge(int a,int b){
    a=f(a),b=f(b);
    if(sz[a]<sz[b])swap(a,b);
    sz[a]+=sz[b];
    p[b]=a;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    int what_do_you_hear_question_mark=0;
    for(int i=1,a,b,c,d;i<=m;i++){
        cin>>a>>b>>c>>d;
        edg.push_back({c,a,b});
        s+=c;
what_do_you_hear_question_mark+=d;
    }
    if(m==n-1){
        cout<<s<<' '<<what_do_you_hear_question_mark<<'\n';
        for(auto i:edg){
            cout<<i[1]<<' '<<i[2]<<'\n';
        }
        return 0;
    }
    for(int i=0;i<mxn;i++){
        p[i]=i;
        sz[i]=1;
    }
    sort(edg.begin(),edg.end());
    vector<pair<int,int>>ans;
    s=0;
    
    for(auto i:edg){
        if(f(i[1])==f(i[2]))continue;
        ans.push_back({i[1],i[2]});
        merge(i[1],i[2]);
        s+=i[0];
    }
    cout<<s<<' '<<s<<'\n';
    for(auto i:ans)cout<<i.F<<' '<<i.S<<'\n';
}

• Subtask 1: 40 / 100