제출 #1128968

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128968		Piokemon	시간이 돈 (balkan11_timeismoney)	C++17	100 / 100	871 ms	968 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

constexpr int N = 200;
constexpr int M = 10'000;
int rep[N+9];
vector<pair<pair<ll,ll>,pair<ll,ll>>> kraw;

int fint(int a){
    if (rep[a]==a)return a;
    return rep[a]=fint(rep[a]);
}

void onion(int a, int b){
    a=fint(a);
    b=fint(b);
    rep[a]=b;
}

ll wa,wb;
bool comp(pair<pair<ll,ll>,pair<ll,ll>> a, pair<pair<ll,ll>,pair<ll,ll>>  b){
    ll aa,bb;
    aa = a.second.first*wa + a.second.second*wb;
    bb = b.second.first*wa + b.second.second*wb;
    return aa<bb;
}
ll best=1e18;
vector<pair<pair<ll,ll>,pair<ll,ll>>> uzyte;
pair<ll,ll> bestt;
pair<ll,ll> wynik;

pair<ll,ll> mst(int n){
    for (int x=0;x<n;x++)rep[x]=x;
    sort(kraw.begin(),kraw.end(),comp);
    pair<ll,ll> odp={0,0};
    uzyte.clear();
    for (auto x:kraw){
        int u,v;
        u =x.first.first; v=x.first.second;
        if (fint(u)==fint(v))continue;
        uzyte.push_back(x);
        onion(u,v);
        odp={odp.first+x.second.first,odp.second+x.second.second};
    }
    ll temp=odp.first*odp.second;
    if (temp<best){
        best=temp;
        bestt={wa,wb};
    }
    wynik=odp;
    return odp;
}


void split(int n, pair<ll,ll> l, pair<ll,ll> r){
    wb=-(l.first-r.first);
    wa=(l.second-r.second);
    pair<ll,ll> nowy=mst(n);
    if (nowy==l || nowy==r || (wa*nowy.first+wb*nowy.second)==(wa*l.first+wb*l.second))return;
    split(n,l,nowy);
    split(n,nowy,r);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,a,b,c,d;
    cin >> n >> m;
    for (int x=0;x<m;x++){
        cin >> a >> b >> c >> d;
        kraw.push_back({{a,b},{c,d}});
    }
    wa=0; wb=1;
    pair<ll,ll> l=mst(n);
    wa=1; wb=0;
    pair<ll,ll> r=mst(n);
    split(n,r,l);
    
    wa=bestt.first; wb=bestt.second;
    mst(n);
    cout << wynik.first << ' ' << wynik.second<<'\n';
    for (auto x:uzyte){
        cout << x.first.first << ' ' << x.first.second << '\n';
    }
    return 0;
}

• Subtask 1: 100 / 100