Submission #238936

#	Time	Username	Problem	Language	Result	Execution time	Memory
238936		jh05013	timeismoney (balkan11_timeismoney)	C++17	100 / 100	500 ms	832 KiB

timeismoney

#include <bits/stdc++.h>
#define sz(X) (int)((X).size())
#define entire(X) X.begin(),X.end()
using namespace std; typedef long long ll;
void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);}
template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;}
template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;}

typedef pair<ll,ll> pll;
// positive -> ccw; negative -> cw; 0 -> collinear
ll ccw(pll a, pll b, pll c){
    auto [ax,ay] = a; auto [bx,by] = b; auto [cx,cy] = c;
    return (bx-ax)*(cy-ay) - (by-ay)*(cx-ax);
}

struct disjointSet{
    vector<int> par;
    disjointSet(int n): par(n) {iota(entire(par), 0);}
    void un(int x, int y){par[fd(x)] = fd(y);} // yr becomes parent
    int fd(int x){return par[x]!=x? (par[x]=fd(par[x])) : x;}
};

typedef tuple<int,int,ll,ll> EDGE;
int n;
vector<EDGE> edges;

tuple<ll, ll, vector<pair<int,int>>>
mst(ll T, ll C){
    sort(entire(edges), [&](const EDGE &e1, const EDGE &e2){
        auto [a1,b1,t1,c1] = e1;
        auto [a2,b2,t2,c2] = e2;
        return T*t1 + C*c1 < T*t2 + C*c2;
    });
    ll ts = 0, cs = 0;
    disjointSet DS(n+1);
    vector<pair<int,int>> ans;
    for(auto [a,b,t,c]: edges){
        if(DS.fd(a) == DS.fd(b)) continue;
        DS.un(a, b), ts+= t, cs+= c;
        ans.push_back({a,b});
    }
    return {ts, cs, ans};
}

tuple<ll,ll,ll> hullsearch(pll l, pll r){
    auto [lt,lc] = l; auto [rt,rc] = r;
    tuple<ll,ll,ll> ltup = {lt*lc,lt,lc}, rtup = {rt*rc,rt,rc};
    auto ans = min(ltup, rtup);
    auto [mt,mc,_] = mst(lc-rc, rt-lt);
    pll m = {mt,mc};
    if(ccw(r, m, l) < 0){
        ans = min(ans, hullsearch(l, m));
        ans = min(ans, hullsearch(m, r));
    }
    return ans;
}

int main(){OJize();
    int m; cin>>n>>m;
    for(int i=0; i<m; i++){
        int a,b,t,c; cin>>a>>b>>t>>c;
        edges.push_back({a,b,t,c});
    }
    auto [x0,y0,__1] = mst(1, 0);
    auto [x1,y1,__2] = mst(0, 1);
    auto [tc,t,c] = hullsearch({x0,y0}, {x1,y1});
    cout<<t<<' '<<c<<"\n";
    auto [__3,__4,TREE] = mst(c, t);
    for(auto [a,b]: TREE) cout<<a<<' '<<b<<'\n';
}

Compilation message (stderr)

timeismoney.cpp: In lambda function:
timeismoney.cpp:30:26: warning: unused variable 'a1' [-Wunused-variable]
         auto [a1,b1,t1,c1] = e1;
                          ^
timeismoney.cpp:30:26: warning: unused variable 'b1' [-Wunused-variable]
timeismoney.cpp:31:26: warning: unused variable 'a2' [-Wunused-variable]
         auto [a2,b2,t2,c2] = e2;
                          ^
timeismoney.cpp:31:26: warning: unused variable 'b2' [-Wunused-variable]
timeismoney.cpp: In function 'std::tuple<long long int, long long int, long long int> hullsearch(pll, pll)':
timeismoney.cpp:49:18: warning: unused variable '_' [-Wunused-variable]
     auto [mt,mc,_] = mst(lc-rc, rt-lt);
                  ^
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:64:20: warning: unused variable '__1' [-Wunused-variable]
     auto [x0,y0,__1] = mst(1, 0);
                    ^
timeismoney.cpp:65:20: warning: unused variable '__2' [-Wunused-variable]
     auto [x1,y1,__2] = mst(0, 1);
                    ^
timeismoney.cpp:66:17: warning: unused variable 'tc' [-Wunused-variable]
     auto [tc,t,c] = hullsearch({x0,y0}, {x1,y1});
                 ^
timeismoney.cpp:68:23: warning: unused variable '__3' [-Wunused-variable]
     auto [__3,__4,TREE] = mst(c, t);
                       ^
timeismoney.cpp:68:23: warning: unused variable '__4' [-Wunused-variable]

• Subtask 1: 100 / 100