제출 #1128974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128974		jamkel	시간이 돈 (balkan11_timeismoney)	C++20	100 / 100	457 ms	756 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;
ll w,wa,wb;
ll kk=3;
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>ww={0,0};
   for(int i=0;i<m;i++)
    {
        if(f(u,a[i].u)!=f(u,a[i].v))
        {
            ww.st+=a[i].a;
            ww.nd+=a[i].b;
            u[u[a[i].u]]=u[a[i].v];
        }
    }
    return ww;
}
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;
        }
    }
}
void q(vector<edge>&a,pair<ll,ll>p,pair<ll,ll>k)
{
    //cout<<k.st<<endl;
   // kk--;
    vb=p.st-k.st;
    va=k.nd-p.nd;
    //cout<<va<<" "<<vb<<endl
   // return;
    pair<ll,ll>www=mst(a);
    //cout<<p.st<<" "<<p.nd<<" "<<k.st<<" "<<k.nd<<" "<<www.st<<" "<<www.nd<<endl;
   // if(kk==0)return;
    if(www==p or www==k or va*www.st+vb*www.nd==p.st*va+p.nd*vb)return;
    if(www.st*www.nd<w)
    {
        wa=va;
        wb=vb;
        w=www.st*www.nd;
    }
    q(a,p,www);
    q(a,www,k);
}
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=0;
  pair<ll,ll>p1=mst(a);
  wa=1;wb=0;w=p1.st*p1.nd;
  va=0;vb=1;
  pair<ll,ll>p2=mst(a);
  if(p2.st*p2.nd<=w)
  {
      wa=0;wb=1;
      w=p2.st*p2.nd;
  }
   // cout<<p1.st<<" "<<p1.nd<<" "<<p2.st<<" "<<p2.nd<<endl;
    
  if(p1!=p2)
  {
    q(a,p2,p1);
  }
  va=wa;vb=wb;
  pair<ll,ll>p3=mst(a);
  cout<<p3.st<<" "<<p3.nd<<endl;
  mstww(a);
}

• Subtask 1: 100 / 100