Submission #1188803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188803		FaresSTH	timeismoney (balkan11_timeismoney)	C++20	85 / 100	2094 ms	820 KiB

timeismoney

#include"bits/stdc++.h"
using namespace std;
using ld=long double;
using ll=long long;
#define S second
#define F first
int p[300],sz[300],T,M,ans=1e9;
vector<pair<int,int>>res,cur;
int fnd(int v){
    if(v!=p[v])p[v]=fnd(p[v]);
    return p[v];
}
void mrg(int a,int b){
    a=fnd(a),b=fnd(b);
    if(sz[a]<sz[b])swap(a,b);
    sz[a]+=sz[b];
    p[b]=a;
}
pair<int,int> ty(ld a,vector<array<int,4>>&ar){
    vector<pair<int,int>>br;
    for(int i=0;i<(int)ar.size();i++){
        br.push_back({a*ar[i][2]+ar[i][3],i});
    }
    sort(br.begin(),br.end());
    for(int i=0;i<300;i++){
        sz[i]=1;
        p[i]=i;
    }
    cur.clear();
    pair<int,int>curr;
    for(auto i:br){
        if(fnd(ar[i.S][0])==fnd(ar[i.S][1]))continue;
        cur.push_back({ar[i.S][0],ar[i.S][1]});
        mrg(ar[i.S][0],ar[i.S][1]);
        curr.F+=ar[i.S][2];
        curr.S+=ar[i.S][3];
    }
    return curr;
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    vector<array<int,4>>a(m);
    for(auto&i:a)cin>>i[0]>>i[1]>>i[2]>>i[3];
    for(int i=0;i<300;i++)p[i]=i;
    for(ld i=1;i<100;i+=1){
        for(ld j=1;j<100;j+=1){
            if(gcd(ll(i),ll(j))>1)continue;
            auto cr=ty(i/j,a);
            if(cr.F*cr.S<ans){
                ans=cr.F*cr.S;
                res=cur;
                T=cr.F;
                M=cr.S;
            }
            // cout<<i<<' '<<j<<endl;
        }
    }
    cout<<T<<' '<<M<<'\n';
    for(auto i:res)cout<<i.F<<' '<<i.S<<'\n';
}

• Subtask 1: 85 / 100