Submission #1214541

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214541		nrg_studio	timeismoney (balkan11_timeismoney)	C++20	50 / 100	2097 ms	131072 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define vec vector

const int MAX_N = 200, MAX_M = 10000;

struct DSU {
    int par[MAX_N], sz[MAX_N];

    int get(int x) {return par[x]==x ? x : par[x]=get(par[x]);}
    bool unite(int a, int b) {
        a = get(a); b = get(b);
        if (a==b) {return false;}
        if (sz[a]<sz[b]) {swap(a,b);}
        par[b] = a; sz[a] += sz[b];
        return true;
    }

    void reset() {
        iota(par,par+MAX_N,0);
        memset(sz,1,sizeof(sz));
    }
};

struct Edge {
    int u, v, t, c;
};
bool cmp1(const Edge& a, const Edge& b) {return a.t<b.t;}
bool cmp2(const Edge& a, const Edge& b) {return a.c<b.c;}
Edge ed[MAX_M];
DSU dsu;
ll c_ans = 1e9, t_ans = 1e9, c_tot, t_tot;
Edge ans[MAX_N], cand[MAX_N];
int n, m;

ll scalex, scaley;
bool cmp3(const Edge& a, const Edge& b) {return scalex*a.t+scaley*a.c<scalex*b.t+scaley*b.c;}

void calc() {
    dsu.reset();
    c_tot = 0, t_tot = 0;
    for (int i=0,ptr=0;i<m;i++) {
        if (dsu.unite(ed[i].u,ed[i].v)) {
            cand[ptr++] = ed[i];
            c_tot += ed[i].c; t_tot += ed[i].t;
            if (ptr==n-1) {break;}
        }
    } if (c_tot*t_tot<c_ans*t_ans) {
        c_ans = c_tot; t_ans = t_tot;
        copy(cand,cand+n-1,ans);
    }
}

void solve(ll ax, ll ay, ll bx, ll by) {
    scalex = ay-by; scaley = bx-ax;
    sort(ed,ed+m,cmp3);
    calc();
    ll cx = t_tot, cy = c_tot;
    //cout << cx << ' ' << cy << '\n';
    if ((bx-ax)*(cy-ay)-(by-ay)*(cx-ax)<=0 && !(cx==ax&&cy==ay) && !(cx==bx&&cy==by)) {
        solve(ax,ay,cx,cy);
        solve(cx,cy,bx,by);
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    for (int i=0;i<m;i++) {cin >> ed[i].u >> ed[i].v >> ed[i].t >> ed[i].c;}

    sort(ed,ed+m,cmp1); calc();
    ll ax = t_tot, ay = c_tot;
    sort(ed,ed+m,cmp2); calc();
    ll bx = t_tot, by = c_tot;
    //cout << ax<<' ' <<ay<<' '<<bx<<' '<<by<<'\n';
    solve(ax,ay,bx,by);
    cout << t_ans << ' ' << c_ans << '\n';
    for (int i=0;i<n-1;i++) {cout << ans[i].u << ' ' << ans[i].v << '\n';}
    

    /*
    set of points (C,T)
    take the MST minimizing C, and the MST minimizing T; then
    all possible answer candidates are on the lower hull between these points

    algorithm: take A, B, find the point under AB with maximum absolute distance
    call it C, then recurse (A,C) and (C,B)

    (i derived quickhull?? (w/ hint on using dnc))

    claim: C is always between A and B
    proof: is C is not between A and B, then either A or B isn't on the hull

    so distance to AB is just perpendicular length = maximizing area of triangle ABC
    (B-A)x(C-A) = (Bx-Ax)(Cy-Ay)-(By-Ay)(Cx-Ax) minimize

    Equivalent to finding a point C with the minimum value of aCx+bCy for constants a,b

    verify that C lies between A and B

    Holy fuck
    it works
    find C can be done with mst algorithm in o(mlogm)

    crazy
    time complexity: NTMlogM i hope it runs
    */
}

• Subtask 1: 50 / 100