Submission #376665

#	Time	Username	Problem	Language	Result	Execution time	Memory
376665		jeroenodb	timeismoney (balkan11_timeismoney)	C++14	100 / 100	470 ms	620 KiB

timeismoney

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 200+1, mxM=1e4+2, oo = 1e9;
typedef complex<int> pt;
#define X real()
#define Y imag()
auto cross(pt u, pt v) {return (ll)u.X*v.Y-(ll)u.Y*v.X;}
auto sgn(ll a) {return a==0?0:(a>0?1:-1);}
auto ccw(pt p1, pt p2, pt p3) {auto u = p2-p1, v = p3-p2;return cross(u,v);}
auto in(pt p1, pt p2) {return (ll)p1.X*p2.X+(ll)p1.Y*p2.Y;}
auto norm(pt p) {return (ll)p.X*p.X+(ll)p.Y*p.Y;}
void read(pt& p) {
    int a,b; cin >> a >> b;
    p = {a,b};
}
struct DSU{
    vector<int> sz,parent;
    int components;
    DSU(int n) {
        sz.assign(n,1);
        components = n;
        parent.resize(n);
        for(int i=0;i<n;++i) parent[i]=i;
    }
    void link(int a, int b) {
        components--;
        if(sz[a]<sz[b]) {
            swap(a,b);
        }
        sz[a] = max(sz[a],sz[b]+1);
        parent[b] = a;
    }
    bool unite(int a, int b) {
        int pa = find(a),pb = find(b);
        if(pa!=pb) link(pa,pb);
        return pa!=pb;
    }
    int find(int a) {
        if(a==parent[a]) return a;
        return parent[a] = find(parent[a]);
    }
};
ll ft,fc;
struct edge{
    int a,b,t,c;
    bool operator<(const edge& o) const {
        return ft*t+fc*c < ft*o.t+fc*o.c;
    }
};
int n,m; 
edge edges[mxM];

int bestfc=0, bestft=1;
ll best=1e18;
complex<int> bestp=0;

pt kruskal(bool print=false) {
    DSU dsu(n);
    sort(edges,edges+m);
    pt ans = 0;
    for(int j=0;j<m;++j) {
        auto& e = edges[j];
        if(dsu.unite(e.a,e.b)) {
            ans+=pt{e.t,e.c};
            if(print) cout << e.a << ' ' << e.b << '\n';
        }
        if(dsu.components==1) break;
    }
    auto score = (ll)ans.X*ans.Y;
    if(score<best) {
        bestp = ans;
        best = score;
        bestft = ft;
        bestfc = fc;
    }
    return ans;
}

void solve(pt ul, pt rd) {
    ft = ul.Y-rd.Y;
    fc = rd.X-ul.X;
    if(ft==fc and ft==0) ft = 1;
    auto nw = kruskal();
    if(ccw(ul,nw,rd)==0) return;
    solve(ul,nw), solve(nw,rd);
}
int main() {
    cin >> n>>m;
    for(int i=0;i<m;++i) {
        int a,b,t,c; cin >> a >> b >> t >> c;
        edges[i] = {a,b,t,c};
    }
    ft = 1, fc = 0;
    auto p1 = kruskal();
    ft = 0, fc = 1;
    auto p2 = kruskal();
    solve(p1,p2);
    cout << bestp.X  << ' ' << bestp.Y << '\n';
    ft = bestft;
    fc = bestfc;
    kruskal(true);
}

• Subtask 1: 100 / 100