Submission #203002

#	Time	Username	Problem	Language	Result	Execution time	Memory
203002		gs18115	timeismoney (balkan11_timeismoney)	C++14	100 / 100	505 ms	760 KiB

timeismoney

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define semicolon ;
#define ryan bear
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
pl operator-(pl x,pl y)
{
    return pl(x.fi-y.fi,x.se-y.se);
}
inline ll ccw(pl x,pl y)
{
    return x.fi*y.se-x.se*y.fi;
}
int pa[205];
int par(int x)
{
    if(pa[x]==-1)
        return x;
    return pa[x]=par(pa[x]);
}
int v,e;
vector<pair<pi,pl> >edges;
inline void sort(const pl&p)
{
    sort(all(edges),[=](pair<pi,pl>&x,pair<pi,pl>&y){return x.se.fi*p.se+x.se.se*p.fi<y.se.fi*p.se+y.se.se*p.fi;});
    return;
}
vector<pi>ae;
pl mst(const pl&p)
{
    sort(p);
    ae.clear();
    fill(pa,pa+v,-1);
    ll ct=0,cc=0;
    for(auto&t:edges)
        if(par(t.fi.fi)!=par(t.fi.se))
            pa[par(t.fi.fi)]=par(t.fi.se),ct+=t.se.fi,cc+=t.se.se,ae.eb(t.fi);
    return pl(ct,cc);
}
ll ans;
pl ai;
void findconvex(pl left,pl right)
{
    pl p=left-right;
    p.se=-p.se;
    pl c=mst(p);
    if(c.fi*c.se<ans)
        ai=p,ans=c.fi*c.se;
    if(ccw(left-c,right-c)>0)
        findconvex(left,c),findconvex(c,right);
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>v>>e;
    edges.resize(e);
    for(auto&t:edges)
        cin>>t.fi.fi>>t.fi.se>>t.se.fi>>t.se.se;
    pl c1=mst(pl(1,65536));
    pl c2=mst(pl(65536,1));
    if(c1.fi*c1.se<c2.fi*c2.se)
        ans=c1.fi*c1.se,ai=pl(1,65536);
    else
        ans=c2.fi*c2.se,ai=pl(65536,1);
    findconvex(c2,c1);
    pl c=mst(ai);
    cout<<c.fi<<' '<<c.se<<endl;
    for(pi&t:ae)
        cout<<'\n'<<t.fi<<' '<<t.se;
    cout<<endl;
    return 0;
}

• Subtask 1: 100 / 100