Submission #223797

#	Time	Username	Problem	Language	Result	Execution time	Memory
223797		brcode	timeismoney (balkan11_timeismoney)	C++14	100 / 100	1117 ms	1016 KiB

timeismoney

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 10010;
long long par[MAXN];
struct point{
    long long w;
    long long u;
    long long v;
    long long t;
    long long c;
    
};
bool cmp(point A,point B){
    return A.w<B.w;
}
long long n,m;
point lines[MAXN];
long long bestt = 1e9;
long long bestc = 1e9;
vector<point> bestres;
long long findpar(long long curr){
    if(par[curr] == curr){
        return curr;
    }
    return par[curr] = findpar(par[curr]);
}
void merge(long long a,long long b){
    a = findpar(a);
    b = findpar(b);
    par[a] = b;
}
point mst(long long dx,long long dy){
 //   cout<<dx<<" "<<dy<<endl;
    for(long long i=1;i<=m;i++){
        lines[i].w = (1LL*lines[i].t*dy)+(1LL*lines[i].c*dx);
        
    }
    sort(lines+1,lines+m+1,cmp);
    for(long long i=1;i<=n;i++){
        par[i] = i;
    }
    long long t= 0;
    long long c = 0;
    vector<point> res;
    for(long long i=1;i<=m;i++){
        
        if(findpar(lines[i].u)!=findpar(lines[i].v)){
            merge(lines[i].u,lines[i].v);
            t+=lines[i].t;
            c+=lines[i].c;
            res.push_back(lines[i]);
        }
    }
    
    if(1LL*t*c<1LL*bestt*bestc){
        bestt =t;
        bestc = c;
        bestres = res;
    }
    point hold;
    hold.u = t;
    hold.v = c;
    //cout<<t<<" "<<c<<endl;
    return hold;
}
void recurse(point A,point B){
    point C = mst(B.u-A.u,A.v-B.v);
    if((1LL*(B.v-A.v)*(C.u-B.u))==(1LL*(C.v-B.v)*(B.u-A.u))){
        return;
    }
    recurse(A,C);
    recurse(C,B);
}
int main() {
    cin>>n>>m;
    for(long long i=1;i<=m;i++){
        cin>>lines[i].u>>lines[i].v>>lines[i].t>>lines[i].c;
        lines[i].u++;
        lines[i].v++;
    }
    point A = mst(0,1);
    point B = mst(1,0);
    
    recurse(A,B);
    cout<<bestt<<" "<<bestc<<endl;
    for(long long i=0;i<(long long)bestres.size();i++){
        cout<<bestres[i].u-1<<" "<<bestres[i].v-1<<endl;
    }
}

• Subtask 1: 100 / 100