Submission #1196780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196780		Newtonabc	timeismoney (balkan11_timeismoney)	C++20	60 / 100	19 ms	584 KiB

timeismoney

#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
using namespace std;
const int N=1e4+10;
int pa[300];
pair<pair<int,int>,pair<int,int>> edge[N];
bool con[N];
bool use[N];
int root(int x){if(pa[x]==x) return x; return pa[x]=root(pa[x]);}
int main(){
    int n,m;
    cin>>n >>m;
    for(int i=1;i<=n;i++) pa[i]=i;
    for(int i=0;i<m;i++){
        cin>>edge[i].f.f >>edge[i].f.s >>edge[i].s.f >>edge[i].s.s;
    }
    long long sa,sb;
    int cnt=0;
    sa=sb=0;
    while(cnt!=n-1){
        long long mn=LLONG_MAX,pick=0;
        for(int i=0;i<m;i++){
            if(con[i]) continue;
            auto [x,y]=edge[i];
            auto [u,v]=x;
            if(root(u)==root(v)){
                con[i]=true;
                continue;
            }
            long long nxt=(sa+(ll)edge[i].s.f)*(sb+(ll)edge[i].s.s);
            if(mn>nxt){
                mn=nxt;
                pick=i;
            }
        }
        con[pick]=true;
        pa[root(edge[pick].f.f)]=root(edge[pick].f.s);
        sa+=(ll)edge[pick].s.f,sb+=(ll)edge[pick].s.s;
        cnt++;
        use[pick]=true;
    }
    cout<<sa <<" " <<sb <<"\n";
    for(int i=0;i<m;i++){
        if(use[i]) cout<<edge[i].f.f <<" " <<edge[i].f.s <<"\n";
    } 

}

• Subtask 1: 60 / 100