Submission #1128964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128964		Piokemon	timeismoney (balkan11_timeismoney)	C++17	50 / 100	2097 ms	49144 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)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: 50 / 100