Submission #937038

#	Time	Username	Problem	Language	Result	Execution time	Memory
937038		Khalid_Alabdullatif	timeismoney (balkan11_timeismoney)	C++14	100 / 100	357 ms	736 KiB

timeismoney

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<ll,int>
using namespace std;
const int N=1e4+7;
struct point{
    point(){}
    point(ll xx, ll yy):x(xx),y(yy){}
    ll x=0,y=0;
    friend point operator+(point a,point b){
        return point(a.x+b.x,b.y+b.y);
    }
    friend point operator-(point a,point b){
        return point(a.x-b.x,a.y-b.y);
    }
    friend ll operator^(point a, point b){
        return a.x*b.y-a.y*b.x;
    }
    friend ll operator*(point a,point b){
        return a.x*b.x+a.y*b.y;
    }
    friend bool operator<(point a,point b){
        if(a.x<b.x)
            return 1;
        if(a.x==b.x){
            if(a.y<=b.y)
                return 1;
            return 0;
        }
        return 0;
    }
    friend bool operator>(point a,point b){
        if(a.x>b.x)
            return 1;
        if(a.x==b.x){
            if(a.y>=b.y)
                return 1;
            return 0;
        }
        return 0;
    }
};
struct edge{
    int v,u,t,c;
};
int n,m;
int par[201],sz[201];
point sol(1e18,1e18),ans;
bool ok[201];
edge e[N];
int get(int x){
    if(x==par[x])
        return x;
    return par[x]=get(par[x]);
}
bool merge(int a,int b){
    a=get(a),b=get(b);
    if(a==b)
        return 0;
    if(sz[a]>sz[b])
        swap(a,b);
    par[a]=b;
    sz[b]+=sz[a];
    return 1;
}
void init(){
    for(int i=0;i<n;i++)
        par[i]=i,sz[i]=1;
}
point mst(point x){
    sort(e,e+m,[&](edge e1,edge e2){
        return (x.x*e1.t + x.y*e1.c)<(x.x*e2.t + x.y*e2.c);
    });
    init();
    point an2st;
    for(int i=0;i<m;i++)
        if(merge(e[i].v,e[i].u))
            an2st.x+=e[i].t,an2st.y+=e[i].c;
    return an2st;
}
void solve(point a,point b){
    point x=b-a;
    point dir=point(-x.y,x.x);
    point an2st=mst(dir);
    if(an2st.x*an2st.y<sol.x*sol.y){
        sol=an2st;
        ans=dir;
    }
    if (((x)^(an2st-a))==0) return;
    solve(a,an2st);
    solve(an2st,b);
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<m;i++)
        cin>>e[i].v>>e[i].u>>e[i].t>>e[i].c;

    point a=mst(point(1, 0));
    sol=a;
    ans=point(1, 0);
    
    point b=mst(point(0, 1));
    if (b.x*b.y < sol.x * sol.y){
        sol=b;
        ans=point(0, 1);
    }
    solve(a,b);
    mst(ans);
    cout<<sol.x<<' '<<sol.y<<endl;
    init();
    for(int i=0;i<m;i++)
        if(merge(e[i].v,e[i].u))
            cout<<e[i].v<<' '<<e[i].u<<endl;
}

• Subtask 1: 100 / 100