제출 #1128952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128952		jamkel	시간이 돈 (balkan11_timeismoney)	C++20	50 / 100	5 ms	584 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nd second
#define st first
struct edge
{
    ll u;
    ll v;
    ll a;
    ll b;
};
ll va,vb;
ll n,m;
bool por(edge &a, edge&b)
{
 return a.a*va+a.b*vb<b.a*va+b.b*vb;
}
ll f(vector<ll>&u,ll i)
{
    if(u[i]==i)return i;
    return u[i]=f(u,u[i]);
}
pair<ll,ll>mst(vector<edge>&a)
{
    sort(a.begin(),a.end(),por);
    vector<ll>u(n);
    for(int i=0;i<n;i++)u[i]=i;
    pair<ll,ll>w={0,0};
   for(int i=0;i<m;i++)
    {
        if(f(u,a[i].u)!=f(u,a[i].v))
        {
            w.st+=a[i].a;
            w.nd+=a[i].b;
            u[u[a[i].u]]=u[a[i].v];
        }
    }
    return w;
}
void mstww(vector<edge>&a)
{
    sort(a.begin(),a.end(),por);
    vector<ll>u(n);
    for(int i=0;i<n;i++)u[i]=i;
   for(int i=0;i<m;i++)
    {
        if(f(u,a[i].u)!=f(u,a[i].v))
        {
            u[u[a[i].u]]=u[a[i].v];
            cout<<a[i].u<<" "<<a[i].v<<endl;
        }
    }
}
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  cin>>n>>m;
  vector<edge>a(m);
  for(int i=0 ;i<m; i++)
  {
      cin>>a[i].u>>a[i].v>>a[i].a>>a[i].b;
  }
  va=1;vb=1;
  cout<<mst(a).st<<" "<<mst(a).nd<<endl;
  mstww(a);
}

• Subtask 1: 50 / 100