Submission #1171377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171377		amirhoseinfar1385	timeismoney (balkan11_timeismoney)	C++20	55 / 100	11 ms	2152 KiB

timeismoney

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

struct yal{
    int u,v,x,y,ax,ay;
    int getad(int fu){
        return (u^v^fu);
    }
};
vector<yal>ally;
int n,m,inf=1e16;
const int maxn=205;

struct dsu{
    int par[maxn];
    int root(int u){
        if(u==par[u]){
            return u;
        }
        return par[u]=root(par[u]);
    }
    int con(int u,int v){
        u=root(u);
        v=root(v);
        if(u!=v){
            par[u]=v;
            return 1;
        }
        return 0;
    }
    void clear(){
        for(int i=0;i<maxn;i++){
            par[i]=i;
        }
    }
    dsu(){
        for(int i=0;i<maxn;i++){
            par[i]=i;
        }
    }
}ds;
pair<int,int>mainres;
int nago=0;

ll area(pii A, pii B, pii P) {
	pii AB = {B.first - A.first, B.second - A.second};
	pii AP = {P.first - A.first, P.second - A.second};
	return AB.first * AP.second - AB.second * AP.first;
}

bool cmp(yal a,yal b){
    if(nago==0){
        return a.ax+a.ay<b.ax+b.ay;
    }
    return a.ax+a.ay>b.ax+b.ay;
}

pair<int,int>findmst(int s,int z,int w=0){
    vector<yal>fake;
    for(int i=0;i<(int)ally.size();i++){
        auto f=ally[i];
        f.ax=f.x*s;
        f.ay=f.y*z;
        fake.push_back(f);
    }
    sort(fake.begin(),fake.end(),cmp);
    pair<int,int>ret={0,0};
    ds.clear();
    vector<pair<int,int>>kh;
    for(int i=0;i<(int)fake.size();i++){
        auto x=fake[i];
        if(ds.con(x.u,x.v)){
            //cout<<x.x<<" "<<x.y<<" "<<x.u<<" "<<x.<<"\n";
            ret.first+=x.x;
            ret.second+=x.y;
            kh.push_back(make_pair(x.u,x.v));
        }
    }
    if(w==1){
        cout<<ret.first<<" "<<ret.second<<"\n";
        for(auto x:kh){
            cout<<x.first<<" "<<x.second<<"\n";
        }
    }
    return ret;
}

void vorod(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        yal x;
        cin>>x.u>>x.v>>x.x>>x.y;
        ally.push_back(x);
    }
}
int res=inf;


bool check(pair<int,int>a,pair<int,int>b,pair<int,int>c){
    return area(a,b,c)<0;
}

void calc(pair<int,int>a,pair<int,int>b){
    //cout<<a.first<<" "<<a.second<<" "<<b.first<<" "<<b.second<<"\n";
    int s=-a.first+b.first;
    int z=-b.second+a.second;
    pair<int,int>tof=findmst(s,z);
    //cout<<"ha: "<<tof.first<<" "<<tof.second<<"\n";
    if(check(a,b,tof)){
        res=min(res,tof.first*tof.second);
        if(tof.first*tof.second==res){
            mainres={s,z};
        }
        calc(a,tof);
        calc(tof,b);
    }
}

void khor(){
    //cout<<mainres.first<<" "<<mainres.second<<"\n";
    findmst(mainres.first,mainres.second,1);
}

void solve(){
    vorod();
    pair<int,int>a=findmst(0,1);
    pair<int,int>b=findmst(1,0);
    nago=0;
    res=min(a.first*a.second,b.first*b.second);
    if(a.first*a.second==res){
        mainres={0,1};
    }else{
        mainres={1,0};
    }
    calc(b,a);
    //cout<<res<<"\n";
    khor();
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    for(int asd=0;asd<t;asd++){
        solve();
    }
}

• Subtask 1: 55 / 100