제출 #1141853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141853		Abdullah_Alodaibi	시간이 돈 (balkan11_timeismoney)	C++20	55 / 100	4 ms	968 KiB

timeismoney

#include "bits/stdc++.h"
using namespace std;
using ll = long long;
struct edge{
    ll t,c,x,y;
};
struct dsus{
    ll boss,size;
};
dsus dsu[205]={};
dsus find(ll a){
    if(dsu[a].boss==a)return dsu[a];
    return dsu[a]=find(dsu[a].boss);
}
void connect(ll x,ll y){
    ll a=find(x).boss,b=find(y).boss;
    if(dsu[a].boss!=dsu[b].boss){
        if(dsu[a].size<dsu[b].size)swap(a,b);
        dsu[b].boss=dsu[a].boss;
        dsu[a].size+=dsu[b].size;
        dsu[b]=dsu[a];
    }
}
ll val(edge a){
    double x=abs(a.c-a.t)/a.c+a.t;
    return a.c+a.t-(x/10);
}
bool cmp(edge a,edge b){
    return val(a)<val(b);
}
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n,m,tt=0,cc=0;
    cin>>n>>m;
    vector<edge> v;
    vector<pair<ll,ll>> ans;
    for(int i=0;i<m;i++){
        ll x,y,t,c;
        
        cin>>x>>y>>t>>c;
        v.push_back({t,c,x,y});
    }
    for(int i=0;i<n;i++)dsu[i]={i,1};
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<m;i++){
        if(find(v[i].x).boss!=find(v[i].y).boss){
            connect(v[i].x,v[i].y);
            ans.push_back({v[i].x,v[i].y});
            cc+=v[i].c;tt+=v[i].t;
        }
        if(ans.size()==n-1)break;
    }
    cout<<tt<<" "<<cc<<"\n";
    for(int i=0;i<ans.size();i++){
        cout<<ans[i].first<<" "<<ans[i].second<<"\n";
    }
}

• Subtask 1: 55 / 100